Количество разделителей строк

leo



Получается, этот способ более гибкий в случае если заранее неизвестно, до каких размеров массив может вырасти. В принципе, я массив не наращиваю, поэтому в данном конкретном случае действовать проще - значит действовать эффективнее. В смысле времени.

 

cresta

"..коллизий типа исключений быть не должно. Неоднократно пробовал - вроде проблем не было."

Дело твое, ты спросил тебе ответили.

S_T_A_S ссылочку дал насчет безопасной работы со стеком - не поленись посмотреть и уточнить свои установки максимального размера стека. У тебя размер массива получается около мегабайта. Если установлен максимальный размер 1 Мб, то будет весело, если вместо 240 000 указателей будет > 262 000.

 

cresta

Про длину строк. Я не имел ввиду фиксированную длину, а хотел сказать, что sort.exe имеет ограничение, на максимальный размер строки. Точную цифру не знаю.



Не понял, Mail Message File что-ли?

MMF - Memory Mapped File. Это когда с файлом работают как с последовательностью байт и нет необходимости заниматься вызовом ReadFile.



Тогда надо будет немалое количество раз заниматься пересылками строк

Какие пересылки строк? В памяти сразу выстраивается упорядоченная последовательность адресов строк. Они (адреса) и двигаются внутри массива. А теперь ответь что быстрее чем двигать dword'ы? Ибо адрес, в твоем случае до 2Гб. - это dword



leo

метод сортировки путем вставки ... бестолковых пересылок

Ты не понял мой алгоритм, я пересылаю только адреса. Прежде чем упоминать известные названия алгоритмов сортировки и указывать VCL компоненты с их методами, подумай, как прикрутить их к конкретной реализации на ассемблере.

 

cresta

"..значит действовать эффективнее. В смысле времени."

Со SparseArray - да, я и сам отметил, что в данном случае он ничего не дает кроме усложнения. Но при VirtualAlloc c MEM_RESERVE усложнения минимальные, зато экономия времени на пересылке мегабайта данных из стека в нужное место, т.к. казатели сразу пишутся куда надо.



q_q

"Ты не понял мой алгоритм, я пересылаю только адреса."

Я и не сомневался, что адреса. Но когда ты добавляешь 240000-й указатель к массиву из N = 239999, и он в результате сортировки должен занять первую позицию, то ты будешь переписывать около 1 Мб данных. И такая ситуация возможна при добавлении любого указателя.

Другими словами, не нужно производить сортировку при добавлении каждого элемента. Нужно сначала загрузить все адреса и затем отсортировать все скопом - получим большую экономию времени.



Что касается VCL, то я привел ссылку на известный алгоритм. А на ассемблере я его использовал не один раз в разных вариантах (не только для строк).



PS: прошу прощения, если задело слово "бестолковых", но оно относилось исключительно к пересылкам. Это уж из области преимуществ и недостатков массивов - хочешь что-то вставить - сдвигай весь хвост. В списках такой проблемы нет.

 

q_q

Если тебе больше по душе метод последовательной вставки строк (ес-но указателей), то вот тебе элементарный способ увеличить его быстродействие почти вдвое - вставлять не одну строку, а две (или более). Двоичным поиском находим индексы вставки i и j, где j > i(если равны сравниваем строки между собой). Затем сдвигаем хвост массива с индекса j сразу на 2 элемента, вставляем указатель j, сдвигаем среднюю часть на 1 элемент и вставляем указатель i. При этом число пересылок сокращается вдвое, а общее быстродействие на больших массивах - почти вдвое.

 

leo

Нужно сначала загрузить все адреса и затем отсортировать все скопом - получим большую экономию времени ... При этом число пересылок сокращается вдвое

Это не более чем слова. Займемся практикой? Тем более, что "на ассемблере ты его использовал не один раз".

 

leo

Мне показалось, что Винда сама переносит рабочую область в PAGE_GUARD, а под PAGE_GUARD выделяет новую область. Так получается, что эти манипуляции только в пределах 1Мб?

Да, я тут поэкспериментировал, на 350000. Действительно, из цикла в котором записывается в стек, программа выходит вообще, т.е. она не падает, Просто до конца цикла (там поставил брейкпоинт) не доходит. Видимо её молча Винда выгрузила и очистила стек. Получается,эээ...Нехорошо. Видимо лучше не в стек, а сразу память под указатели.



q_q

Эта тема как-раз появилась вследствие того, что я решил заняться с одним товарищем практикой

Если leo не будет против, то у меня будет просьба: если можно, то с аттачами и комментариями. А если по какой-либо причине не сможет, давай со мной. Я понимаю, что ты меня побьёшь, но для интереса можно с какой-нибудь форой (в смысле ты мне фору даёшь ).

 

А ну займитесь, займитесь. Любопытно мне будет посмотреть. Насколько я понял, q_q говорит о сортировке вставками.

http://algolist.manual.ru/sort/insert_sort.php



Хотя, Адрес первой строки помещаю в начало массива. Читаю очередную строчку и методом половинного деления беру из массива адрес строки для сравнения с очередной. Как только нашел место очередной строки в массиве, то вставляю ее, все которые больше двигаются вниз.

больше смахивает на гибрид, т.к. q_q утверждает, что берет следующий элемент "методом половинного деления".



leo предлагает qsort.

Insertion Sort относится к классу O(N²).

Quick Sort относится к классу O(N*Ln(N)).



q_q - ты, если я тебя понял правильно, не просто вдуешь. Ты пролетишь как фанера над Парижем.

 

Чавой-то я не понял - чего вы от меня хотите.

Если реализацию борландовского QuickSort, то извольте. Боюсь, правда, навлечь гнев "дZенствующих", но я обожаю Object Pascal и расставаться с ним в ближайшем столетии не собираюсь. Поэтому для начала, оригинальный "пасквильный" вариант c некоторой заменой идентификаторов (для ясности):

Код (Text):

1. procedure QuickSort(SortList: pPointerList; FromIndex,ToIndex:integer);
2. //SortList -  массив указателей на строки или любые другие объекты
3. //FromIndex и ToIndex - начальный и конечный индексы диапазона сортировки
4. //(процедура вызывается  рекурсивно при разных FromIndex,ToIndex)
5. //далее CompareFunc - функция сравнения данных D1 и D2 по указателям P1 и P2, которая возвращает Result < 0 если "D1 < D2", = 0 при "D1 = D2" и > 0 при "D1 > D2"
6. var
7.   L,R:integer;
8.   P,Temp:pointer;
9. begin
10.   //внешний цикл
11.   repeat
12.     L:=FromIndex; //левый индекс диапазона
13.     R:=ToIndex;   //правый индекс диапазона
14.     P:=SortList^[(FromIndex + ToIndex) shr 1]; //элемент в середине
15.     //внутренний цикл
16.     repeat
17.       //ищем элемент >= P слева
18.       while CompareFunc(SortList^[L], P) < 0 do Inc(L);
19.       //ищем элемент <= P справа
20.       while CompareFunc(SortList^[R], P) > 0 do Dec(R);
21.       //если что-то нашли
22.       if L <= R then
23.       begin
24.         //перестановка элементов L и R  
25.         Temp:=SortList^[L];
26.         SortList^[L]:=SortList^[R];
27.         SortList^[R]:=Temp;
28.         Inc(L);
29.         Dec(R);
30.       end;
31.     until L > R; //перехлест, больше искать нечего
32.     //если элемент <= P найден, то рекурсивный вызов  
33.     if FromIndex < R then
34.       QuickSort(SortList,FromIndex,R);
35.     //когда рекурсия закончилась предвигаем нижнюю границу
36.     FromIndex:=L;
37.   until L >= ToIndex;
38. end;

Как это все работает, и насколько дает выигрыш ("скоко в граммах"), я разбирался немало лет тому назад и счас с ходу не скажу. Знаю что много, "скоко" - проверьте сами.

(Кстати при рекурсивном вызове есть теоретическая опасность stack overflow, но на практике такого не бывает. Когда-то я проверял максимальное число вложенных вызовов, но опять же - "скоко" не скажу, т.к. "не очень много").



Для тех, кто лучше разбирается в asm-е, чем в pas-ле, вот рыба (или мясо), опять же для пасквильного register call:

Код (Text):

1. //procedure QuickSort(SortList:pointer;FromIndex,ToIndex:integer); register;
2. //на входе: eax = buf, edx = FromIndex, ecx = ToIndex
3. //asm
4.     push    ebx
5.     push    ebp
6.     push    esi
7.     push    edi
8.     push    edx     //esp+4 = FromIndex
9.     push    ecx     //esp = ToIndex
10.     mov     esi, eax    //esi = SortList
11.  
12.     mov ebx, edx    //ebx = LeftIndex
13. @@loop1: //------- внешний цикл -----------------
14.     mov     edi, [esp]      //edi = RightIndex
15.     mov     eax, ebx
16.     add     eax, edi
17.     shr     eax, 1
18.     mov     ebp, [esi+eax*4] //контрольная строка в середине диапазона
19.  
20. @@loop2: //--- внутренний цикл ---------
21.     dec ebx
22. @@SearchLeft:  
23.     inc     ebx
24.     invoke  CompareFunc [esi+ebx*4], ebp  //подставь сюда свой вариант вызова
25.     cmp     eax,0
26.     jl      @@SearchLeft
27.    
28.     inc edi
29. @@SearchRight: 
30.     dec     edi
31.     invoke  CompareFunc [esi+edi*4], ebp //аналогично
32.     cmp     eax,0
33.     jg      @@SearchRight
34.    
35.     cmp     ebx,edi
36.     jg      @@stop
37.     je  @@inc
38.     //меняем строки местами
39.     mov     eax, [esi+ebx*4]
40.     mov     ecx, [esi+edi*4]
41.     mov     [esi+ebx*4], ecx
42.     mov     [esi+edi*4], eax
43. @@inc:
44.     inc     ebx
45.     dec     edi
46.     cmp     ebx,edi
47.     jle     @@loop2 //<--- внутренний цикл ----
48.  
49. @@stop: //если RightIndex достиг FromIndex
50.     cmp     [esp+4],edi
51.     jge     @@next
52.     //иначе рекурсивный вызов QuickSort(Buf,FromIndex,RightIndex)
53.     mov     ecx, edi
54.     mov     edi,[esp+4]
55.     mov     eax, esi
56.     call    QuickSort  
57. @@next:
58.     mov     [esp+4], ebx   //новое значение FromIndex = LeftIndex
59.     cmp     ebx, [esp]     //если LeftIndex достиг ToIndex -> конец
60.     jl      @@loop1 //<--- внешний цикл -------------------
61.    
62.     pop     ecx
63.     pop     edx
64.     pop     edi
65.     pop     esi
66.     pop     ebp
67.     pop     ebx
68.     ret
69. //end;

 

q_q, cresta & примкнувший к ним volodya

"Займемся практикой"

Вот и займитесь. От меня тут толку не много, т.к. я использую asm только для развлечения или там, где он дает реальный выигрыш в "килограммах" по сравнению с API или дельфи. Например, приведенная выше asm-реализация QuickSort мало чем отличается от дельфийской и что тут можно еще существенно наоптимизировать - я не знаю. По крайней мере по быстродействию.



Для меня более интересный вопрос в данной задаче - это информация о длинах строк. Она вроде бы и есть в момент формирования массива (как разность адресов соседних указателей), а когда начинаем сортировать массив - то все теряем. Если файл загружен в память, то наверное можно заменить все 0D0A на StrLen:word. Или как ? При каждом сравнении строк делать проверку на 0D ?

 

leo

А если StrLen попадёт в диапазон печатных символов? Т.е. к примеру встретилось в строке: 6565h - это что, длина или строка "AA"? Не определишь. И как может повлиять на сравнение тот факт, знаешь длину строки или нет? Имхо, никак.

 

cresta

у меня будет просьба: если можно, то с аттачами и комментариями ... А если по какой-либо причине не сможет,давай со мной.

ok.



в смысле ты мне фору даёшь

А надо? В чем она будет измеряться?



volodya

А ну займитесь, займитесь ... не просто вдуешь. Ты пролетишь как фанера над Парижем

Провоцируешь? Не страшно. Если моя реализация окажется хуже в сравнении с чьей-то, то я приобрету новые знания.



leo

Чавой-то я не понял - чего вы от меня хотите.

Реализацию сортировки текстового файла. Параметры имя сортируемого и имя результирующего файла.



Вот и займитесь.

Т.е. я один? Зачем тогда рассуждения о бестолковых пересылках?



2 leo, volodya & cresta

Не буду засорять эту ветку. Обдумаю проект постановки задачи и создам новую ветку в этом же разделе.

 

q_q



У меня уже есть проект, если интересно

Ну давай так, попробуем

 

cresta

У меня уже есть проект, если интересно

Я завел "Сортировка строк текстового файла." Давай про сортировку там, а тут про концы строк.

 

cresta

"И как может повлиять на сравнение тот факт, знаешь длину строки или нет?"

В рассматриваемом случае строки заканчиваются на 0D0A, а не на 0. Поэтому использовать апишную CompareStringA можно только при известных длинах ссhCount. Хотя, конечно, эта функция очень тормозная на русском тексте, особенно без учета регистра. Контроль окончания строки нужен в любом случае. Либо нужно проверять сравниваемые символы каждой из строк на 0D, либо ограничить число сравнений наименьшим значением из двух длин, если они известны.



"StrLen попадёт в диапазон печатных символов?"

Ну и что ? Если при загрузке файла зарезервировать два первых байта под длину первой строки, то в итоге мы получим гибридный аналог паскалевских строк - два байта длина строки, затем сама строка. Не подумай, что я настаиваю на таком варианте - вопрос задан только ради интереса.



q_q

Чего-то ты брат, по-моему, кипятишься. Я уже принес свои извинения за некорректные слова. Так что предлагаю забыть обиды и "дружить семьями".

Что касается проекта, то я уже сказал, что использую Delphi с ассемблерными вставками. Поэтому с чистым asm-проектом помочь не могу. Но определенный опыт в сортировке строк есть. Несколько лет тому назад замутил нехилую прогу для автоматизированного разбора текста и автозагрузки полученной таблицы в БД (сводные данные о земельных участках и их владельцах). Сортировок там хоть отбавляй (и текст по нескольким столбцам, и по числовым значениям). И требования по скорости для интерактивного режима, сам понимаешь, высокие, иначе - нервирует. Вот, правда, оптимальное количество строк оказалось на уровне не более 8-10 тыс. - иначе оператор дуреет и тонет в мусоре.



Резюме: чем могу - помогу, если есть конкретные вопросы.

 

leo

принес свои извинения

Слово не воробей. Либо искупай делом, либо прекращай бить себя кулаком в грудь "...определенный опыт в сортировке строк есть. Несколько лет тому назад замутил нехилую прогу...".

 

q_q

1) Тебе предложенного asm-варианта QuickSort мало ? Или хочешь заполучить законченную прогу ?

Вариант абсолютно рабочий, нужно только заменить invoke CompareFunc на конкретный call функции сравнения двух строк. Если строки кончаются нулем, то для пробы можно использовать CompareString минус 2. А еще проще, чтобы только убедиться, что такой вариант быстрее - попробуй сортировать не строки, а значения dword самих указателей (считай, что это массив целых чисел). Тогда CompareFunc это просто P1-P2.



2) Сам-то чего-нибудь предложи. А то в новой ветке поставил суперзадачу и собираешься ждать по несколько километров однотипных решений ? Хоть бы рыбу предложил для обсуждения.



3) И еще: что значит " в формате ASCII". Русские буквы есть или ASCII 128 ? Если есть, то в какой кодировке ? Сортировка с учетом регистра или нет ? И потом "размер файла до 2^63" - это для прикола или ты встречал такие тексты ? Такими заявами ты народ можешь отпугнуть от обсуждения.

 

leo

Тебе предложенного asm-варианта QuickSort мало

Меня не интересует реализации алгоритмов сортировки на различных языках программирования. Меня интересна полноценная подпрограмма(мы) которые из одного файла делают другой. Особенно та ее(их) часть, которая готовит данные для сортировки.



Сам-то чего-нибудь предложи.

Я не отказываюсь и НАПИШУ код. Для начала необходимо оговорить условия. Если комментариев не будет, то напишу по своим предложенным.



Хоть бы рыбу предложил для обсуждения.

Я не ставлю целью оценить свой код. Напротив хочу увидеть разные подходы.



И еще: что значит ...

Там четко написано, какие коды допустимы до 0FFh.



И потом размер файла до 2^63

Я больше не могу. У меня ntfs



ps если хочешь участвовать, то комментарии и вопросы там.

 

q_q

Причем тут ntfs ? Ты что, весь винт собрался отсортировать ? Я тебя спрашиваю: где ты видел текстовые файлы размером более сотни (ну сотен) мегабайт ? А если видел, то для чего их сортировать по строкам ? При таких размерах разумнее использовать СУБД с индексными файлами и перестраивать индексы, а не сам супер-мега-гига-файл.

 

leo

Если у тебя есть замечания, то изложи их в той ветке, пожалуйста.

Про 63 бита, чтобы не рассчитывать, что размер файла можно описать 32-ух-битным регистром.