masquer
при чем здесь кол-во строк
Я так думаю, что автор смотрит именно на количество строк, не обращая внимания на количество абзацев.

„Я так думаю, что автор смотрит именно на количество строк, не обращая внимания на количество абзацев.“
Ну, для того, чтобы кол-во _строк_ подсчитать нужно действительно знать и размеры листа, и margins, и кучу параметров шрифта и пр. :)
Если для текста, то хотя бы органичитель для длины строки. А так 0d0a это и будет абзац.

cresta
Суть использования VirtualAlloc или SparseArray состоит именно в том, что не нужно заранее знать размер результирующего массива.
Например, при использовании VirtualAlloc с флагом MEM_RESERVE можно сразу зарезервировать адресное пространство равное размеру файла (ну или 1/2,1/3 - хотя при резервировании это большой роли, не играет если речь не идет о гигабайтах,т.к. при этом никакой физической памяти не выделяется). Далее возможны два подхода. "Классический" - выделять память, используя MEM_COMMIT, блоками фиксированного размера: если после очередного inc индекс в ebx превышает размер выделенной памяти - выделяешь следующий блок по адресу BaseAddr+(ebx-1)*4. Другой подход - менее "элегантный" - сразу выделить достаточный размер памяти MEM_COMMIT. Если внимательно читать Win32.hlp, то увидим, что "The system initializes and loads each committed page into physical memory only at the first attempt to read or write to that page", т.е. пока мы не добрались до какой-то commited страницы - физической памяти она не занимает. В этом случае по завершении формирования массива делаем VirtalFree, освобождая лишнюю память.

Суть использования SparseArray, также состоит в том, что мы пишем указатели в текущий блок, а когда он заполняется - выделяем новый и пишем в него. Ссылки на начало блоков хранятся в отдельном массиве. Конечно такой метод алгоритмически сложнее, чем VirtualAlloc. Но в отличие от последнего он не требует размещения всех блоков по последовательным адресам в памяти (sparse = разбросанный). Каждый блок может распределяться GlobalAlloc и лежать по произвольным адресам - где системе будет угодно. Конечно если ты загрузил массив в одной процедуре и все, то SparseArray никчему. А вот если к существующему массиву нужно добавить новый массив строк, то при обычном подходе нужно делать ReAlloc и переписвать кучу указателей, а в случае SparseArray - только указатели на блоки.

q_q

„Зачем? Тебе необходимо рисовать прогресс сортировки?“

Строки произвольной длины, до 2Гб. Если бы были фиксированной длины, то начало строки можно было бы просто рассчитать. А в случае переменной длины расчёт невозможен, поэтому составляю массив указателей на начала строк. Чтобы потом сортировать по указателям.

„Как только нашел место очередной строки в массиве, то вставляю ее, все которые больше двигаются вниз.“

Тогда надо будет немалое количество раз заниматься пересылками строк. С учетом возможной длины строк и их количества около 300 000 - Это время. А с указателями я исходный массив строк не трогаю, только сами указатели переставляю. После сортировки беру последовательно указатели и соответствующие им строки пихаю в новый кусок памяти, который выгружаю в файл. Т.е. пересылка строк - один раз, уже после сортировки. А может и этой пересылки строк можно будет избежать, если WriteFile позволит делать append. Надо будет глянуть.

„Ты используешь mmf?“

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

За аттач спасибо.


S_T_A_S_

„imho ничего страшного в этом нет, но нужно знать несколько моментов:“

Единственная операция с загруженым стеком - вызов VirtualAlloc. И тут же разгрузил его. Мне кажется, коллизий типа исключений быть не должно. Неоднократно пробовал - вроде проблем не было.

q_q
На больших массивах метод сортировки путем вставки очередной строки работает медленно из-за большого числа бестолковых пересылок. Гораздо лучше в плане быстродействия загрузить строки как есть, а затем использовать известный алгоритм QuickSort (опять же ссылаюсь на Borland Delphi или C Builder: TStringList.QuickSort). Работает гораздо быстрее.

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
„будет весело, если вместо 240 000 указателей будет > 262 000.“
Мне показалось, что Винда сама переносит рабочую область в 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 некоторой заменой идентификаторов (для ясности):

procedure QuickSort(SortList: pPointerList; FromIndex,ToIndex:integer);
//SortList -  массив указателей на строки или любые другие объекты
//FromIndex и ToIndex - начальный и конечный индексы диапазона сортировки
//(процедура вызывается  рекурсивно при разных FromIndex,ToIndex)
//далее CompareFunc - функция сравнения данных D1 и D2 по указателям P1 и P2, которая возвращает Result < 0 если "D1 < D2", = 0 при "D1 = D2" и > 0 при "D1 > D2"
var
  L,R:integer;
  P,Temp:pointer;
begin
  //внешний цикл
  repeat
    L:=FromIndex; //левый индекс диапазона
    R:=ToIndex;   //правый индекс диапазона
    P:=SortList^[(FromIndex + ToIndex) shr 1]; //элемент в середине
    //внутренний цикл
    repeat
      //ищем элемент >= P слева
      while CompareFunc(SortList^[L], P) < 0 do Inc(L);
      //ищем элемент <= P справа
      while CompareFunc(SortList^[R], P) > 0 do Dec(R);
      //если что-то нашли 
      if L <= R then
      begin
        //перестановка элементов L и R  
        Temp:=SortList^[L];
        SortList^[L]:=SortList^[R];
        SortList^[R]:=Temp;
        Inc(L);
        Dec(R);
      end;
    until L > R; //перехлест, больше искать нечего
    //если элемент <= P найден, то рекурсивный вызов  
    if FromIndex < R then 
      QuickSort(SortList,FromIndex,R);
    //когда рекурсия закончилась предвигаем нижнюю границу
    FromIndex:=L;
  until L >= ToIndex;
end;

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

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

//procedure QuickSort(SortList:pointer;FromIndex,ToIndex:integer); register;
//на входе: eax = buf, edx = FromIndex, ecx = ToIndex
//asm
	push    ebx
	push    ebp
	push    esi
	push    edi
	push    edx		//esp+4 = FromIndex
	push    ecx		//esp = ToIndex
	mov     esi, eax	//esi = SortList

	mov	ebx, edx	//ebx = LeftIndex
@@loop1: //------- внешний цикл -----------------
	mov     edi, [esp]      //edi = RightIndex
	mov     eax, ebx
	add     eax, edi
	shr     eax, 1
	mov     ebp, [esi+eax*4] //контрольная строка в середине диапазона

@@loop2: //--- внутренний цикл ---------
	dec ebx
@@SearchLeft:	
	inc     ebx 
	invoke  CompareFunc [esi+ebx*4], ebp  //подставь сюда свой вариант вызова
	cmp     eax,0
	jl      @@SearchLeft
	
	inc edi	
@@SearchRight:	
	dec     edi
	invoke  CompareFunc [esi+edi*4], ebp //аналогично
	cmp     eax,0
	jg      @@SearchRight
	
	cmp     ebx,edi
	jg      @@stop
	je	@@inc
	//меняем строки местами
	mov     eax, [esi+ebx*4]
	mov     ecx, [esi+edi*4]
	mov     [esi+ebx*4], ecx
	mov     [esi+edi*4], eax
@@inc:
	inc     ebx
	dec     edi
	cmp     ebx,edi
	jle     @@loop2 //<--- внутренний цикл ----

@@stop: //если RightIndex достиг FromIndex
	cmp     [esp+4],edi 
	jge     @@next
	//иначе рекурсивный вызов QuickSort(Buf,FromIndex,RightIndex)
	mov     ecx, edi
	mov     edi,[esp+4]
	mov     eax, esi
	call    QuickSort  
@@next:	
	mov     [esp+4], ebx   //новое значение FromIndex = LeftIndex
	cmp     ebx, [esp]     //если LeftIndex достиг ToIndex -> конец
	jl      @@loop1 //<--- внешний цикл -------------------
	
	pop     ecx
	pop     edx
	pop     edi
	pop     esi
	pop     ebp
	pop     ebx
	ret
//end;

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

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