Részhalmazgyártó

Munkahelyi feladat szokott lenni, hogy rendezett listák (gyakorlatilag halmazok) egymáshoz való viszonyát kell kideríteni. Két listával még kézileg el lehet bánni a comm parancs segítségével. (Az egyszerűbb használat kedvéért definiáltam a comm1, comm2, comm3 parancsot, amelyek a comm -23, comm -13, comm -12-nek felelnek meg).

Viszont 4 halmaznál már célszerűbbnek látszott szkriptet írni. Meg is született egy változat:
http://pastebin.com/QPfB755T – s aztán próbáltam rajta gyorsítani: http://pastebin.com/s3Kf505G
Ilyen méretű fájlokkal, ahol a sorok száma: 1107100, 210700, 526700, 447400, 17 másodpercig futott az eredeti, és 14-ig a gyorsított program. Ha ismertek erre az alapfeladatra kifinomultabb algoritmust, akkor örömmel veszem az ötleteket.

( asch v | 2014. 05. 14., sze – 11:21 )

Ha jól értem, attól függ, hogy egy bejegyzés melyik fájlba kerül, hogy melyik fájlokban van benne. Ha az elsőben és a harmadikban, akkor megy az s1010-ba, igaz?

Én programot írnék rá, ami mind a négy fájlt egyszerre olvassa soronként, mindig a legkisebb kulcsot veszi ki az összes folyamból, ahol ez a kulcs van legelől. Ahol ez volt legelől, annak megfelelő mintájú kimeneti fájlba (folyamba) teszi a kulcsot. Tehát az összes kimeneti fájlt is egyszerre nyitnám meg, és írnám. Ezzel a módszerrel minden fájlt pontosan egyszer kell végigolvasni, és minden kimeneti bejegyzés CPU költsége annyi, amennyibe a négy elem sorbarendezése kerül - tehát lényegében semmi a végigolvasáshoz képest.

Ha a bemenet olvasását és a kimenet írását megfelelően (jó nagy, és a diszk blokkmérettel összhangban lévő blokkokat használva) puffereled, akkor a végrehajtás sebessége kb a diszk olvasás/íráséval lesz azonos.