วิธีการเรียงลำดับตัวอักษรและตัวเลขใน Unix ด้วยการเรียงลำดับ? ซับซ้อนกว่าที่เห็น

ฉันกำลังพยายามจัดเรียงสตริงตัวอักษรและตัวเลขตามตัวอักษรและตัวเลขด้วยวิธี "ใช้งานง่าย"/เป็นธรรมชาติโดยใช้คำสั่ง unix sort แต่ไม่สามารถจัดเรียงได้อย่างถูกต้อง ฉันมีไฟล์นี้:

$ cat ~/headers 
@42EBKAAXX090828:6:100:1699:328/2
@42EBKAAXX090828:6:10:1077:1883/2
@42EBKAAXX090828:6:102:785:808/2

ฉันต้องการจัดเรียงตามตัวอักษร โดยที่ @42EBKAAXX090828:6:10:... อยู่อันดับแรกตามสัญชาตญาณ (เนื่องจาก 10 น้อยกว่า 100 และ 102) อันดับสองคือ @42EBKAAXX090828:6:100... และอันดับสามคือ @42EBKAAXX090828:6:102:204:1871/2

ฉันรู้ว่าแนะนำให้เรียงลำดับตำแหน่งเฉพาะภายในบรรทัด แต่ตำแหน่งของ : ที่นี่อาจแตกต่างกัน ดังนั้นนี่จึงไม่ใช่วิธีแก้ปัญหาทั่วไปและใช้งานได้ที่นี่

ฉันเหนื่อย:

sort --stable -k1,1 ~/headers > foo

โดยมีพารามิเตอร์ -n และ -u ผสมกันหลากหลาย แต่ไม่ได้ให้ลำดับที่ถูกต้อง

สิ่งนี้สามารถทำได้อย่างมีประสิทธิภาพทั้งจาก bash โดยใช้ sort หรือจาก Python ฉันต้องการนำไปใช้กับไฟล์ที่มีขนาดประมาณ 4-5 GB ดังนั้นจึงมีบรรทัดหลายล้านบรรทัด

ขอบคุณ!


python bash shell sorting unix
person Community    schedule 06.12.2011    source แหล่งที่มา
comment
โปรดทราบว่าสิ่งนี้มักเรียกว่าการเรียงลำดับตามธรรมชาติ   -  person yak    schedule 06.12.2011
comment
ไม่แน่ใจเกี่ยวกับประสิทธิภาพ แต่นี่คือการใช้งานการเรียงลำดับตามธรรมชาติใน python: stackoverflow.com/q/4836710/331473   -  person Adam Wagner    schedule 06.12.2011
comment
คุณจะจัดการกับ @42EBKAAXX09082*7*:6:100:1699:328/2 และ @42EBKAAXX09082*8*:6:100:1699:328/2 (*s เพื่อเน้นย้ำ) อย่างไร พวกเขาเรียงลำดับเหมือนกันหรือเปล่า? (เช่นเฉพาะฟิลด์ที่ 3 เท่านั้นที่เกี่ยวข้อง) คำตอบของ @ JonathanM นั้นดีที่สุด ไม่อย่างนั้นก็ลองดูของฉันสิ   -  person tobyodavies    schedule 06.12.2011

คำตอบ (3)


arrow_upward
11
arrow_downward

ตัวเลือก -V ดูเหมือนจะทำสิ่งที่คุณต้องการ - การเรียงลำดับตามธรรมชาติ มีไว้สำหรับหมายเลขเวอร์ชันอย่างชัดเจน (เพราะฉะนั้นตัวอักษรที่เลือก)

sort -V ~/headers

เอาท์พุท

@42EBKAAXX090828:6:10:1077:1883/2
@42EBKAAXX090828:6:100:1699:328/2
@42EBKAAXX090828:6:102:785:808/2
person tobyodavies    schedule 06.12.2011
comment
ซึ่ง ofc ไม่มีเอกสาร ~~~~~ - person user528025; 07.06.2013
comment
@ user528025 ไม่ มีการบันทึกไว้ ฉันพบตัวเลือกนี้โดยค้นหา man page เพื่อการเรียงลำดับตามธรรมชาติ - person tobyodavies; 11.06.2013

arrow_upward
4
arrow_downward

มัน กำลัง เรียงลำดับตามตัวอักษรตามตัวอย่างของคุณ เหตุผลที่ 10: อยู่หลัง 100 และ 102 ก็เพราะว่า 10: อยู่ เนื่องจากเครื่องหมายทวิภาค : อยู่หลังอักขระ 9 ใน แผนภูมิ ASCII

หากคุณต้องการเรียงลำดับฟิลด์ที่สามโดยคั่นด้วยเครื่องหมายโคลอน ให้ลองทำดังนี้:

sort -t':' -k3 ~/headers > foo
person Jonathan M    schedule 06.12.2011
comment
คำตอบที่ดีถ้า OP ต้องการเรียงลำดับในฟิลด์นั้นเท่านั้น - person tobyodavies; 06.12.2011
comment
อาจดีกว่าถ้าใช้ -k3n หรือ -k3,4n เพื่อให้ 9 เรียงลำดับก่อน 10 มีพื้นที่ให้คิดว่า OP อาจต้องการให้ '@43ZQRY101112:6:19:221:134/3' เรียงลำดับตามแถวที่แสดงแทนที่จะเป็นอันดับที่สอง ดังนั้นการเรียงลำดับอาจต้องใช้คีย์มากกว่าคีย์ที่สาม น่าสนใจที่จะทราบว่าข้อมูล '@6NBGD010101:9:99:999:111/3' หรือ '@213QED081231:16:91:23:2/0' อาจปรากฏขึ้นหรือไม่ และตำแหน่งเหล่านี้ควรปรากฏสัมพันธ์กับแถวหรือไม่ เริ่มต้น '@42E' ปัญหาคือยังไม่ได้รับการระบุไว้ เนื่องจากเราไม่มีภาพรวมความแปรปรวนของข้อมูลที่เข้ามา - person Jonathan Leffler; 06.12.2011
comment
@JonathanLeffler ค่อนข้างเป็นไปได้ ความคิดเห็นที่ดี ขอบคุณ. - person Jonathan M; 06.12.2011
comment
@JonathanLeffler: ขอบคุณที่ชี้ให้เห็นสิ่งนี้ เพื่อให้ชัดเจน ลำดับคือให้ปฏิบัติต่อ ':' เสมือนว่าเป็นลำดับความสำคัญจากสูงไปต่ำในรูปแบบทศนิยม ดังนั้น 6:500 มาก่อน 7:10 และ 2:200 มาก่อน 6:500 นี่คือเหตุผลที่ฉันไม่คิดว่าวิธีแก้ปัญหาการเรียงลำดับหมายเลขฟิลด์โคลอนโดยเฉพาะจะได้ผล มีทางเลือกอื่นนอกเหนือจากนั้นหรือไม่? ขอบคุณ. - person ; 06.12.2011
comment
คำตอบที่แท้จริงที่สุดคือฉันต้องการให้เหมือนกับวิธีที่โปรแกรม samtools พร้อมตัวเลือก samtools sort -n เรียงลำดับ แต่น่าเสียดายที่ฉันไม่สามารถหาคำอธิบายที่แน่ชัดเกี่ยวกับขั้นตอนการเรียงลำดับที่ใช้ได้ทุกที่... มีใครรู้บ้าง ? - person ; 06.12.2011
comment
@ user248237: คุณสนใจเกี่ยวกับลำดับสัมพัทธ์ของฟิลด์ก่อนเครื่องหมายทวิภาคแรกหรือไม่? เป็นฟิลด์การเรียงลำดับที่สำคัญที่สุดหรือน้อยที่สุด และการเรียงลำดับ 'ลำดับชุดโค้ดแบบตรง' ตกลงสำหรับฟิลด์แรกหรือไม่ หากคุณต้องการเพียง 4 ฟิลด์หลังเครื่องหมายทวิภาคแรกจนถึงเครื่องหมายทับที่เรียงลำดับตามตัวเลข sort -t: -k2,3n -k3,4n -k4,5n -k5,6n ก็ควรทำตามนั้น หากคุณต้องการดูแลฟิลด์แรกเป็นพิเศษ มันจะซับซ้อนมากขึ้น - person Jonathan Leffler; 06.12.2011
comment
มีบทความที่สวยงามเรื่อง 'ทฤษฎีและการปฏิบัติในการสร้างกิจวัตรการเรียงลำดับการทำงาน' โดย JP Linderman ในตอนท้าย มันแสดงให้เห็นว่าวิธีที่ดีที่สุด (หรืออย่างน้อยก็เป็นวิธีที่ดี) ในการปรับปรุงประสิทธิภาพการเรียงลำดับบนคีย์ที่ซับซ้อนคือการเขียนโค้ดการแปลงที่วางคีย์ไว้ที่ด้านหน้าของแต่ละบรรทัดในรูปแบบที่เรียงลำดับได้ง่าย จากนั้น ป้อนข้อมูลไปยังการเรียงลำดับหลัก จากนั้นดึงคีย์การเรียงลำดับออกจากบรรทัดเอาต์พุต ซึ่งจะช่วยลดค่าใช้จ่ายในการตีความแต่ละบรรทัด จึงทำให้การเรียงลำดับเร็วขึ้น น่าเศร้าที่กระดาษนี้หาได้ยากบนอินเทอร์เน็ต Google ค้นหาข้อมูลอ้างอิงแต่ไม่พบบทความ - person Jonathan Leffler; 06.12.2011
comment
@ user248237 หากคุณต้องการให้ : ทำหน้าที่เป็นตัวคั่นขนาดและดูคำตอบของฉัน - person tobyodavies; 06.12.2011

arrow_upward
0
arrow_downward

ซึ่งมักเรียกว่าการเรียงลำดับตามธรรมชาติ นี่เป็นวิธีหนึ่งที่ใช้ได้ผลกับชุดข้อมูลตัวอย่างของคุณ

import re

def natural_sorted(iterable, reverse=False):
    """Return a list sorted the way that humans expect."""
    def convert(text):
        return int(text) if text.isdigit() else text
    def natural(item):
        return map(convert, re.split('([0-9]+)', item))
    return sorted(iterable, key=natural, reverse=reverse)

ฉันพบที่นี่ และ ดีขึ้นเล็กน้อย

person yak    schedule 06.12.2011
comment
สิ่งนี้จะเพิ่มขึ้นเมื่อเทียบกับการเรียงลำดับ Unix หรือไม่ มันสามารถทำงานกับไฟล์ยาวหลายล้านบรรทัดได้หรือไม่? - person ; 06.12.2011