Mehrfache Dateien finden u. automatisch durch hard links ersetzen?

[Chawki]

Und was macht das Ding?
Sellbst Assembler ist leichter zu lesen als Perl.

[edgewalker]

Genau das was ich bereits sagte -- alle Dateien, denen stat() eine Anzahl Hardlinks > 1 ausweist, werden in einen Hash von Arrays gesteckt, der nach Device+Inode aufgeschlüsselt ist. Danach wird der Inhalt des Hashes ausgegeben.

[Chawki]

Achso, ein Array von Hash-Werten; das geht beim Ersetzen der hard links auch (aber nicht beim Erstellen, bei dem Duplikate ersetzt werden).
Nach einmaligem qsort auf das Array bekommt man anschließend mit bsearch schnell heraus, ob eine Datei ein hard link ist.

Ob das effizienter ist, als mit qsort alle Dateien zu sortieren und dabei (als Nebeneffekt, so wie bei dupmerge) hard links zu expandieren, hängt wohl vom Einzelfall ab.
Das O(n*ln(n)) mit qsort reicht mir.

[edgewalker]

Nein, ein Hash von Arrays! Nicht ein Array von Hashwerten!

Übrigens: das Assembler-Äquivalent zu obigem Code wäre Hunderte Zeilen lang. Ob das einfacher zu lesen wäre, als der Perl-Code, sei dahingestellt.

[Chawki]

Original erstellt von edgewalker
Nein, ein Hash von Arrays! Nicht ein Array von Hashwerten!

Was soll das sein?
Gib' mal eine URL, mit der man herausbekommen kann, was Du meinst.

[Chawki]

Also nach einiger googelei habe ich die Antwort auf Seiten wie

http://www.infos24.de/perle/handbuch/7_ ... n_hash.htm

gefunden, aber ohne spezielle Hardware kann so ein Zugriff weder im Mittel noch allgemein in O(1) erfolgen; dafür brächte man Spezial-Hardware wie Assoziativ-Speicher, aber damit kann man auch Sachen wie allgemeines Sortieren mit O(n) machen; wenn der Rechner zudem mind. n CPUs hat, geht es sogar in O(1).

[edgewalker]

Doch, kann er.

http://en.wikipedia.org/wiki/Hash_table

[Chawki]

Also das O(1) pro Element ist falsch, denn beispielsweise beim balancierten Binärbaum als Implementierung hat man O(ln(n)); wie soll da O(1) rauskommen können?

[edgewalker]

Indem man das Element gar nicht erst sucht.. mit den assoziativen Speichern lagst du garnicht so falsch, aber Hardware braucht man dafür nicht.

Hast du die Definition durchzulesen? Hier ist eine, die weiter auf die Theorie eingeht, falls dir die andere zu knapp war:
http://ciips.ee.uwa.edu.au/~morris/Year ... ables.html

[Chawki]

Achso; einfach in einem Hash-Array nachsehen reicht ja, wenn man nur die Hard links einträgt und Kollisionen berücksichtigt

Naja, im worst case hat man O(n) und wenn man einen balancieren Binärbaum nimmt O(ln(n)), so dass ich bei qsort bleibe

[edgewalker]

Der worst case bei einem Hash ist aber unwahrscheinlicher als dreimal sechs Richtige im Lotto -- Durchschnitt ist O(1). Der balancierte Binärbaum braucht O(log n) im Durchschnitt, und der Sortieralgorithmus sogar O(n log n).

Aber nimm ruhig die O(n log n)-Lösung.

[Chawki]

Du verwechselt das; O(1) wäre der best case für n Elemente - ingesammt also O(n) im best case. Demgegenüber ist O(n*ln(n)) nicht viel schlechter, zumal ja bei einer Anwendung noch additive u. multiplikative Konstanten wichtig sind und beim Hash sicherlich O(ln(n)) realistisch ist durch die Kollsionen.

[edgewalker]

Stimmt, da hab ich Eier und Bananen verglichen. Nochmal die Anzahl Schritte, bis man eine traversierbare Struktur hat:

Hash: einfach n-mal einfügen: n * O(1)

Liste+Sortieren: n-mal einfügen dann sortieren: n * O(1) + O(n log n)

Binärbaum: n-mal einfügen und balancieren: n * O(log n) + x

Wir haben also O(n) mit dem Hash und O(n log n) bei beiden anderen Methoden, wobei der Binärbaum in der Praxis wohl ein gutes Stück schlechter abschneidet.

[Chawki]

Naja, das mit dem O(1) beim Hash setzt voraus, dass es wenig Kollisionen gibt, aber bei den einigen hunderttausend Dateien in meiner noch kleinen CD/DVD-Sammlung wird es wohl nicht gerade wenige Kollisionen geben.

Zudem denke ich auch an Skalierbarkeit; bei ähnlichen Dateien kann man mit qsort benachbarte Dateien leicht auf ihre Änlichkeit leicht testen, während es mit Hashes komplizierter ist, insbesondere mit variable vorgebbarer Ähnlichkeit wie z. B. Hamming-Distanz.

[edgewalker]

Die Anzahl der Kollisionen hängt vom Füllgrad des Hashes ab (es sei denn, die Hashing-Funktion ist schlecht) -- und die libc-Hashtable-Funktionen vergrössern den Hash bei Bedarf. Ich habe in Perl schon oft problemlos mit Hashes von ein paar zehntausend Einträgen Grösse hantiert.

Allerdings beisst du dir mit dem Argument grosser Zahlen selber in den Hintern, denn gerade bei n=100.000 wird der Unterschied zwischen O(n) und O(n log n) schon deutlich spürbar...

Ausserdem verstehe ich nicht, was du von DVDs faselst; die Problemstellung ist, dass du herausfinden möchtest, welche Hardlinks zu welchen merfach verlinkten Inodes gehören, um sie auseinanderkopieren zu können. Für das Szenario sind DVDs doch von vornherein irrelevant.

[Chawki]

Ich meine die CD/DVD-Sammlung auf Festplatte und auch rekursive Downloads von irgendwelchen LANs. Mit hard linking kann man einiges an Platz sparen
Trotzdem warte ich auf reiser4, das auch transparente Kompression hat

[R0Y2]

warum warten? reiser4 is released!

[Chawki]

Bisher konnte ich nicht sehen, dass transparente Kompression schon implementiert ist. Bei ext2 ist die Kompression ja nie offiziell verfügbar gewesen; es gab nur ein paar Patches, aber auch nur für uralte Kernel.