сортиране на файл ???

Здравейте!
Подхвърлете някоя идея за сортиране на файл съдържащ запис структори (еднакви структори с различно съдържание).

Благодря Ви!

mi... po kakyw priznak da se sortirat?
towa koeto si mislia che iskash e da imash syotwetstwie na wseki zapis
niakakyw kluch,
prawish si edna struktura (key, offset) ofseta e e offset na zapisa s tozi kluch
w file, i taka. tazi struktura se predpolaga da e po-malka ot originalnata.
prawish niakakwo edno BTree i sled towa ako iskash moje i da prochetesh
zapisite w sortirana polsedowatelnost i da gi zapishesh w now file
ili da prawish merge sort - zarejdash niakakwa chast ot file w pametta
qsort, sled towa merge sys sortorania do momenta file.
wse pak ako na zapisa ot file ti syotwetstwa srawnitelno kys kluch
e dobre da sortirash niakak si edin takyw file sys zapisi (key, offset)
na takyw file mu wikat index :)
poneje mai wednyj goworeshe za towa sam da si indexirash file.

function ReadRec(long nRecNum, MY_REC_TYPE *pRec)
{
OS_depended_seek(OS_depended_handle_to_opened_file, nRecNum * sizeof(MY_REC_TYPE));
OS_depended_read_from_file(OS_depended_handle_to_opened_file, pRec, sizeof(MY_REC_TYPE));
}

function WriteRec(long nRecNum, MY_REC_TYPE *pRec)
{
OS_depended_seek(OS_depended_handle_to_opened_file, nRecNum * sizeof(MY_REC_TYPE));
OS_depended_write_to_file(OS_depended_handle_to_opened_file, pRec, sizeof(MY_REC_TYPE));
}


function BubbleSort()
{
MY_REC_TYPE rec1, rec2;

OpenFile();

long nRecordsNum = FileSize / sizeof(MY_REC_TYPE);

for(long n=0; n<nRecordsNum-2; n++)
{
ReadRec(n, &rec1);
ReadRec(n+1, &rec2);

If (Compare(&rec1, &rec2))
{
WriteRec(n, &rec2);
WriteRec(n+1, &rec1);
}
}

CloseFile();
}

mda... wsyshnost mai ne sa ti haresali predlojeniata na prednia wypros
koito si zadal, mai reshi che wmesto da indexirash shte wzemesh da go
sortirash? hm.
ia kaji kakyw e problema po-konkretno :)

Е, обхождането, разбира се, се повтаря докато не останат елементи за разместване

Това естествено, е най-бавният вариант, за бързина ще трябва да си направиш индексиране в ОП.

moje wsyshnost pyrwo da zapishesh wsichki sortirani parcheta i
sled towa da gi merge-nesh... taka mai zwuchi po-dobre

Идея:
Виж в някоя книга как се прави merge sort. Най общо идеята се състои в прочитане на част от файла, сортирането й в паметта по някой от бързите методи (например qsort - има я в Borland C). След това записваш сортирания буфер във файл. След това четеш следващ буфер, сортираш го сливаш* с вече сортирания първи буфер във втори файл и изтриваш първия временен. Продължаваш така докато не се изчерпа несортирания файл. Накрая във временния се намира сортирания пръвоначален файл.
P.S. Намери си от някъде "Алгоритни + структури от данни = програми" на Вирт той е по-добър в обясненията от мен.
* сливането е все едно да вземеш едно тесте от карти, и да го сортираш :гледаш двете най-горни карти, и която е "по-малка" я слагаш най-отгоре, след това другата ....

МиГ,
Зная, че разбираш ... и ако ти е удобно подскажи (само идеята) може ли и как се използва стандартната библиотечна функция qsort в C за случая когато данните са във файл и не ми стига памет да ги заредя.

Чул съм, че в продукти като Oracle, ... те винаги си държат индексите сортирани като ползват неща като B-Tree. Все пак се налага да сортират и в движение, когато юзера online дава нови Query-та с опция за сортиране. И работи при огромни файлове!
Как мислиш че го правят? (горе-долу, само идеята)

qsort я има във всяко C, понеже е по стандарта на ANSI.

Както и да е, сливането ли е най бързия метод, когато файла е голям и не можеж дори ключовете да заредиш в паметта?

Няма ли да е по-бързо ако се създаде един нов B-Tree индекс и стъпка по стъпка му добавяш всеки ключ от файла? Ако файла има N записа За да вмъкнем в дървото нов ключ ни трябва по-малко от log(N) операции, ... значи всичко N*log(N), което е скоростта на QSORT. Самия B-Tree индекс си е върху диска, но ние можем да кешираме някои от страницитe.

Не зная какво е по-добре. Прасто питам!

Честно казано незнам! Аз съм пробвал това, което съм написал по-горе и работи доста прилично. Като пример сортира и индексира файл със 700 000 записа със големина на записа около 1к за около 15 минути. Компютъра е включен в локална мрежа с NOVELL. Е, буферирането е в XMS и има доста опимизации, но метода е същия.

Нда, славя се като голям разбирач
qsort може да се използва доста ефективно в случая

я дай малко подробности - големина на записа (надявам се да е константна, иначе - ), и брой на записите във файла
също така по кой член на записа трябва да се сортират

а, и с колко памет разполагаш?

брой записи : 1 000 000
големина на записа : 1 К
големина на ключа : 13 bytes
Свободна памет : 200 КB
Свободно дисково пространство : 500 МB
OS : MS DOS
Процесор : Pentium 166
още?

Данните са доста реалистични, за компютър, работещ под MS DOS. Свободната памет е толкова, защото сме заели малко и с код.
Горе долу за колко време мислиш че ще можеш да сортираш този файл?
P.S. Ако искаш можеш да добавш и 16MB XMS...

Това значи 1 гига файл? :)
Сериозна работа :)

Добро предизвикателство. Сега ще изгенерирам един пробен файл и ще ти кажа за колко се сортира.

Всъщност, да ти кажа, ако искаш макс. бързина ще трябва да си направиш и достъп до якия файл с данните през индексен файл, демек своя си БД :)

Здравейте отново!
Май изгубих нишката......
В крайна сметка ше обобщители кой е най бълзия начин за сортиране.
Става дума за сиртиране на файла (програма на С) съдържащ структори от вида:

struct xxx {
long KEY;
char name[40]
} *p;

Целта ми е едно копие на файла да бъде сортирано във възходящ ред спряма KEY и второ копие соптирано по азбучен ред спрямо name.

Целта ми е колко то се може по-голяма бързина.


И два странични въпроса:
какво точно означава XMS и B-Tree

Знам че нямам достатъчно познания и съм се хвърлил в дълбоките води без спасителен пояс, но това не ми дава мира.

shtom iskash faila sortiran po razlichni kriterii izpolzvai index a ne sortirai samia fail

Пламен

Защо наистина не ползваш индексен файл?

pl/sql-1red

there's someone in my head but it's not me
PINK FLOYD