Форум » [x]Harbour » [?] asort() в Harbour » Ответить

[?] asort() в Harbour

subbota: asort() в Harbour неправильно работает ( Может кто-то знает где взять правильную ? ) Вот тест: #include "minigui.ch" #include "hbextcdp.ch" Function Main local ar := {} aadd( ar, { 10, "2" } ) aadd( ar, { 1, "1" } ) aadd( ar, { 11, "3" } ) aadd( ar, { 11, "4" } ) asort( ar,,, {|x,y| x[1] <= y[1] } ) //....................Должно быть....Показывает @ 3, 1 say ar[1,2]//...1..............1 @ 4, 2 say ar[2,2]//....2...............3 @ 5, 3 say ar[3,2]//.....3...............2 @ 6, 4 say ar[4,2]//......4...............4 set exact on asize( ar, 0 ) aadd( ar, { "10", "2" } ) aadd( ar, { "1", "1" } ) aadd( ar, { "11", "3" } ) aadd( ar, { "11", "4" } ) asort( ar,,, {|x,y| x[1] <= y[1] } ) //....................Должно быть....Показывает @ 13, 1 say ar[1,2]//...1..............1 @ 14, 2 say ar[2,2]//....2...............3 @ 15, 3 say ar[3,2]//.....3...............2 @ 16, 4 say ar[4,2]//......4...............4 inkey(0) RETURN NIL

Ответов - 36, стр: 1 2 All

Pasha: ASORT использует для своей работы алгоритм qsort: https://ru.wikipedia.org/wiki/Быстрая_сортировка Естественно, что при равенстве элементов первичный порядок этих элементов не сохраняется, да и другие алгоритмы сортировки этого не предполагают. INDEX ON и SORT ON используют другие алгоритмы, в которых первоначальный порядок равных элементов тоже в общем случае не сохранится. В каких-то примерах он сохранится, но это дело случая. Использование другого алгоритма сортировки приведет лишь к тому, что первоначальный порядок будет нарушен в других случаях. Если так необходимо сохранить исходный порядок для равных элементов, можно поступить следующим образом: добавить индекс подмассива в каждый элемент подмассива: i := 0 AEval(ar, {|a| AADD(a, ++i)}) и затем отсортировать массив по двум индексам: ASORTA(ar, 1, 3) функцию ASORTA я приводил чуть выше.

Dima: Двинул все в новую тему.

Sergy: subbota пишет: Это все-таки существенная недоработка asort() и если разработчики ее устранят, то в Harbour будет одним подводным камнем меньше. C чего Вы решили, что это ошибка? Посмотрите любую книгу по теории программирования. Алгоритмов сортировки - миллион. И ни в одном из них не выполняется требование сохранения исходного порядка записей в случае равенства сравниваемых значений. Основное их требование - эффективность выполнения. Что ASORT() с успехом и выполняет. То же и про sort on. Замена index on на sort on и на asort() не должна провоцировать получения неидентичных резудьтатов. Тоже самое касается индексов. Ваш частный пример в 4 записи - вовсе не показатель. Вы себе вообще представляете структуру индекса? Это двоичное дерево. В зависимости от количества элементов в его ветви, записи могут как сохранить свое исходное положение, так и поменяться местами. Сделайте тест в десяток тысяч записей и посмотрите на результат.


subbota: Sergy пишет: Сделайте тест в десяток тысяч записей и посмотрите на результат. Взял произвольный двумерный массив в 71000 записей (неиндексированная база данных товаров на складе ), перекачал его в dbf и проиндексировал по первому полю Результат вывел в текстовый файл Затем сделал аналогичное после сортировки массива функцией аналогичной asort(), но не делающей перестановок соседних элементов в случае равенства их ключей и при условии сравнения <= Два полученных текстовых файла совпали по содерхимому. Кажется, про то, что после индексации по неубыванию значения ключа, записи с одинаковым его значением должны идти в порядке увеличения физического номера записи, я когда-то прочитал здесь http://mathmod.bmstu.ru/Docs/History/clipper95.html но уверенно назвать источник этой информации сейчас не могу Эксперимент показал что index on работает именно так. И это логично с точки зрения устранения неоднозначности результатов. и почему-бы asort() не делать так же, ведь условие x <= у говорит о том что элементы не надо менять местами, если предыдущий ключ меньше следующего или равен ему

nick_mi: Я тоже НЕ встречал, чтобы при индексации записи с одинаковыми ключами переставлялись местами, запись с большим физическим номером всегда были после записи с меньшим физическим номером. Индексы NTX.

Dima: subbota пишет: Эксперимент показал что index on работает именно так. Тогда и используйте его для сортировки + hbmemio

Pasha: subbota пишет: Эксперимент показал что index on работает именно так. И это логично с точки зрения устранения неоднозначности результатов. и почему-бы asort() не делать так же, ведь условие x <= у говорит о том что элементы не надо менять местами, если предыдущий ключ меньше следующего или равен ему Да, index on использует другой метод сортировки, там идет построение B+ дерева ключей. А asort и sort on используют алгоритм qsort. asort ничего не знает про блок кода, какое там идет сравнение: < или <=. asort только выполняет этот блок кода, и, если он вернет .t., то элементы переставлять не надо, а если .f. - надо. Во время сравнения первоначальный порядок уже другой, так как постоянно идет перестановка элементов. Чтобы первоначальный порядок сохранялся, надо использовать другой метод. Думаю, что простейшая сортировка пузырьком сохранит первоначальный порядок равных элементов. Но такая задача для asort вообще не стоит, главное - использовать быстрый и эффективный алгоритм. И не стоит забывать о главной цель харбора - как можно более полной совместимости с клиппером. asort в клиппер, судя по всему, использует тот же алгоритм qsort.

subbota: Pasha пишет: не стоит забывать о главной цель харбора - как можно более полной совместимости с клиппером. asort в клиппер, судя по всему, использует тот же алгоритм qsort. Посмотрел core-master\src\vm\asort.c Наверно достаточно там в hb_itemIsLess() заменить все < на <= Хотел попробовать, но не смог правильно собрать свой пример ( ну и ладно, раз все-равно совместимость потеряется ), но при этом заинтересовался HBMK2.exe А именно: почему после моей замены harbour.exe на пересобранный, HBMK2.exe продолжает компилировать .prg со старым номером версии harbour.exe Я совсем удалил harbour.exe, а HBMK2.exe все равно работает. Он что и компилятор в себе содержит ? Понимаю, что вопрос не по теме, но не знаю как образуются новые темы и задавался ли где-то этот вопрос раньше. В любом случае благодарю за уделенное мне внимание.

Dima: subbota пишет: Он что и компилятор в себе содержит ? Да с путями что то не так , разбираться надо. Как происходит сборка , что в PATH ?

SergKis: subbota возможно дело в obj файлах (остались старые). сделайте типа такое: if exist .\bin\.hbmk\win\bcc\*.obj del .\bin\.hbmk\win\bcc\*.obj > nul

Pasha: subbota пишет: Посмотрел core-master\src\vm\asort.c Наверно достаточно там в hb_itemIsLess() заменить все < на <= Нет. Во-первых, неважно, какое там сравнение, первоначальные индексы будут нарушены и для <, и для <=. Во-вторых, если задан 4-й параметр, то не делается вообще никакого сравнения, а просто выполняется блок кода: [pre2] if( pBlock ) { hb_vmPushEvalSym(); hb_vmPush( pBlock ); hb_vmPush( pItem1 ); hb_vmPush( pItem2 ); hb_vmSend( 2 ); if( pBaseArray->nLen <= nLast ) return HB_FALSE; else { PHB_ITEM pRet = hb_param( -1, HB_IT_ANY ); /* CA-Cl*pper always takes return value as logical item * accepting 0, 1 as numeric representation of HB_FALSE/HB_TRUE */ if( HB_IS_LOGICAL( pRet ) || HB_IS_NUMERIC( pRet ) ) return hb_itemGetL( pRet ); else return HB_TRUE; } } [/pre2] который возвращает логическое значение. Его результат и анализируется. А что там в этом блоке кода - asort про это не знает. Кстати, я когда-то давал здесь функцию asorta, написанную на C, которая как раз делает сортировку двумерного массива по одному или сразу по двум индексам. Работает быстро, примерно как asort без указания блока кода, а не в 30 раз медленнее. Все-таки выполнение блока кода не проходит даром. Если интересно, могу поискать. Но алгоритм сортировки там точно такой же, что и у asort.

Dima: Pasha пишет: Если интересно, могу поискать. Павел это не эта тема случаем http://clipper.borda.ru/?1-0-0-00000475-000-10001-0-1276757268

Pasha: Да, там есть эта функция, в той теме это ASORTA2

petr707: Для приведения к единому варианту заявителю топика предлагаю вариант, полностью управляемый: массив загоняется во временную таблицу, можно hbmemio далее - INDEX или SORT - по вкусу, затем обратно - из DB-> в массив При размерах массивов больше некоторого порога работа с таблицами быстрее и проще

Dima: petr707 пишет: массив загоняется во временную таблицу, можно hbmemio далее - INDEX или SORT - по вкусу, затем обратно - из DB-> в массив Dima пишет: subbota пишет: цитата: Эксперимент показал что index on работает именно так. Тогда и используйте его для сортировки + hbmemio уже выше предлагалось.

subbota: Меня интересовало приведение к единому результату работы asort(), sort on и index on в самом Harbour. Я полагал, что он от этого станет лучше. Раз это невозможно, то вопрос исчерпан. Благодарю за другие решения.



полная версия страницы