Vraag Unix sorteren voor gedeeltelijk geordende gegevenssets


Ik heb dus een enorm groot bestand (ongeveer 10 GB) en moet het sorteren, net als bij het gebruik van het hulpprogramma 'sorteren', maar een stuk effectiever.

Het probleem is dat ik geen geheugen, CPU-kracht, tijd of vrije wisselruimte heb om de hele soort van stroom te voorzien.

Het goede ding is dat het bestand al gedeeltelijk is geordend (ik kan zeggen dat de afstand van elke regel tot zijn uiteindelijke positie minder is dan een waarde N). Dit soort doet me denken aan het klassieke computerklas voorbeeld van het gebruik van Heapsort met een hoop maat N voor dit doel.

Vraag: Is er een Unix-tool die dat al effectief doet, of moet ik er zelf een coderen?

Bedankt -MK


7
2018-03-24 09:08


oorsprong




antwoorden:


Het zou gemakkelijker zijn om het bestand in kleinere secties op te splitsen en te sorteren. Splitsen: -

split --lines=100000 large_file file_part.

Sorteer vervolgens elk van die door normale sortering te gebruiken

for suffix in `ls file_part.* | cut -f2 -d.` 
do 
  sort file_part.${suffix} > file_sorted.${suffix} 
done

je kunt dan combineren met sortering samenvoegen

sort -m file_sorted.*

Dat zou veel eenvoudiger voor je machine moeten zijn.


12
2018-03-24 09:31



goed idee:] Ik moet alleen het bestand splitsen naar lijnen, maar dit kan worden gedaan met splt -l 100000. Bedankt - exa
Goed punt. Antwoord gewijzigd om regels te ontvangen ... Ik vermoed dat ik de 10 Gb heb gelezen en daarna heb ik die op --bytes gezet .. - Decado
maar je moet het nog twee keer doen, toch? wanneer je 11211222 hebt en door elke 4 wordt gedeeld, ga je 1121 1222 sorteren. Wanneer je het weer samenvoegt, heb je 111212222 - stew
@stew. Zodra je de splitsing "split --lines = 10000 big_file file_part." hebt gedaan, voer je een standaard sortering uit voor elk bestand. dus "sort file_part.aa> file.sorted.aa", dan zul je samensmelten alle delen samen sorteren "sorteer -m file.gesort. *". Dat zal ze combineren en correct bestellen. Misschien is de oorspronkelijke sorteerstap niet duidelijk gemaakt. - Decado


Sorteren, gebruiken en R-weg samenvoeg sorteeralgoritme. De snelste manier om je werk te doen, zou zijn:

sort myfile

dit impliceert O (n logn) tijdcomplexiteit en O (n) tijd.

Als u de gegevens partitioneert, betaalt u deze waarschijnlijk in termen van tijd.

De bovenstaande code heeft een probleem. Met het type -m worden de bestanden niet gegarandeerd onderling gesorteerd.

uit de Unix-handleiding:

   -m, --merge
          merge already sorted files; do not sort

bijv.

file1: a b c k l q file2: d e m

sort -m file1 file2 

a b c k l q d e m

die niet in soort is.

Ook het feit dat de elementen zich op plaatsen bevinden die kleiner zijn dan N, garandeert geen gesorteerde uitvoer met de bovenstaande code:

bestand: a e b c d h f g

in het bestand N = 3 en alle elementen minder dan 3 plaatsen dan hun juiste plaats

file1: h f g, file2: b c d, file3: a e

sort file1

produceert:

file1: f g h, file2: b c d, file3: a e

en

sorm -m file3 file2 file1

uitgangen:

a e b c d f g h

dat niet klopt.


-1
2018-03-24 14:15



Je hebt dat verkeerd. Met je commando's sort file1 enz., alleen de uitvoer is gesorteerd, niet het echte bestand, omdat sorteren standaard naar stdout schrijft. Als je dat doet sort -m daarna past u een mergesort toe op nog ongesorteerde bestanden, wat niet werkt, omdat het vooraf gesorteerde bestanden verwacht. Maar de sort man-pagina is op dit moment duidelijk verkeerd. - Sven♦
volgens de verklaring van SvenW. Eigenlijk doen wat ik suggereer met je waarden lijkt goed te werken op mijn machine. - Decado