Отправлено: 27.05.15 10:39. Заголовок: [?] asort() в Harbour

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

 Отправлено: 29.05.15 21:06. Заголовок: ASORT использует для..

ASORT использует для своей работы алгоритм qsort:

https://ru.wikipedia.org/wiki/Быстрая_сортировка

Естественно, что при равенстве элементов первичный порядок этих элементов не сохраняется, да и другие алгоритмы сортировки этого не предполагают.
INDEX ON и SORT ON используют другие алгоритмы, в которых первоначальный порядок равных элементов тоже в общем случае не сохранится.
В каких-то примерах он сохранится, но это дело случая. Использование другого алгоритма сортировки приведет лишь к тому, что первоначальный порядок будет нарушен в других случаях.
Если так необходимо сохранить исходный порядок для равных элементов, можно поступить следующим образом: добавить индекс подмассива в каждый элемент подмассива:

i := 0
AEval(ar, {|a| AADD(a, ++i)})

и затем отсортировать массив по двум индексам:

ASORTA(ar, 1, 3)

функцию ASORTA я приводил чуть выше.

 Отправлено: 29.05.15 22:53. Заголовок: Двинул все в новую т..

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

 Отправлено: 29.05.15 23:24. Заголовок: subbota пишет: Это ..

subbota пишет:

цитата:

Это все-таки существенная недоработка asort() и если разработчики ее устранят, то в Harbour будет одним подводным камнем меньше.

C чего Вы решили, что это ошибка? Посмотрите любую книгу по теории программирования. Алгоритмов сортировки - миллион. И ни в одном из них не выполняется требование сохранения исходного порядка записей в случае равенства сравниваемых значений. Основное их требование - эффективность выполнения. Что ASORT() с успехом и выполняет.

цитата:

То же и про sort on. Замена index on на sort on и на asort() не должна провоцировать получения неидентичных резудьтатов.

Тоже самое касается индексов. Ваш частный пример в 4 записи - вовсе не показатель. Вы себе вообще представляете структуру индекса? Это двоичное дерево. В зависимости от количества элементов в его ветви, записи могут как сохранить свое исходное положение, так и поменяться местами. Сделайте тест в десяток тысяч записей и посмотрите на результат.

 Отправлено: 30.05.15 03:01. Заголовок: Sergy пишет: Сделай..

Sergy пишет:

цитата:

Сделайте тест в десяток тысяч записей и посмотрите на результат.

Взял произвольный двумерный массив в 71000 записей

(неиндексированная база данных товаров на складе ),

перекачал его в dbf и проиндексировал по первому полю

Результат вывел в текстовый файл

Затем сделал аналогичное после сортировки массива функцией аналогичной asort(),
но не делающей перестановок соседних элементов в случае равенства их ключей
и при условии сравнения <=

Два полученных текстовых файла совпали по содерхимому.

Кажется, про то, что после индексации по неубыванию значения ключа,
записи с одинаковым его значением должны идти в порядке увеличения физического номера записи,
я когда-то прочитал здесь

http://mathmod.bmstu.ru/Docs/History/clipper95.html

но уверенно назвать источник этой информации сейчас не могу

Эксперимент показал что index on работает именно так.

И это логично с точки зрения устранения неоднозначности результатов.

и почему-бы asort() не делать так же, ведь условие x <= у

говорит о том что элементы не надо менять местами,

если предыдущий ключ меньше следующего или равен ему

 Отправлено: 30.05.15 07:17. Заголовок: Я тоже НЕ встречал, ..

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

 Отправлено: 30.05.15 13:00. Заголовок: subbota пишет: Эксп..

subbota пишет:

цитата:

Эксперимент показал что index on работает именно так.

Тогда и используйте его для сортировки + hbmemio

 Отправлено: 01.06.15 12:26. Заголовок: subbota пишет: Эксп..

subbota пишет:

цитата:

Эксперимент показал что index on работает именно так. И это логично с точки зрения устранения неоднозначности результатов. и почему-бы asort() не делать так же, ведь условие x <= у говорит о том что элементы не надо менять местами, если предыдущий ключ меньше следующего или равен ему

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

 Отправлено: 02.06.15 17:28. Заголовок: Pasha пишет: не сто..

Pasha пишет:

цитата:

не стоит забывать о главной цель харбора - как можно более полной совместимости с клиппером. asort в клиппер, судя по всему, использует тот же алгоритм qsort.

Посмотрел core-master\src\vm\asort.c

Наверно достаточно там в hb_itemIsLess() заменить все < на <=

Хотел попробовать, но не смог правильно собрать свой пример

( ну и ладно, раз все-равно совместимость потеряется ),

но при этом заинтересовался HBMK2.exe

А именно: почему после моей замены harbour.exe на пересобранный,

HBMK2.exe продолжает компилировать .prg со старым номером версии harbour.exe

Я совсем удалил harbour.exe, а HBMK2.exe все равно работает.

Он что и компилятор в себе содержит ?

Понимаю, что вопрос не по теме, но не знаю как образуются новые темы

и задавался ли где-то этот вопрос раньше.

В любом случае благодарю за уделенное мне внимание.

 Отправлено: 02.06.15 17:38. Заголовок: subbota пишет: Он ч..

subbota пишет:

цитата:

Он что и компилятор в себе содержит ?

Да с путями что то не так , разбираться надо.
Как происходит сборка , что в PATH ?

 Отправлено: 02.06.15 18:10. Заголовок: subbota возможно де..

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

 Отправлено: 02.06.15 19:13. Заголовок: subbota пишет: Посм..

subbota пишет:

цитата:

Посмотрел core-master\src\vm\asort.c Наверно достаточно там в hb_itemIsLess() заменить все < на <=

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

   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; 
       } 
    } 
 

который возвращает логическое значение. Его результат и анализируется. А что там в этом блоке кода - asort про это не знает.
Кстати, я когда-то давал здесь функцию asorta, написанную на C, которая как раз делает сортировку двумерного массива по одному или сразу по двум индексам.
Работает быстро, примерно как asort без указания блока кода, а не в 30 раз медленнее. Все-таки выполнение блока кода не проходит даром.
Если интересно, могу поискать. Но алгоритм сортировки там точно такой же, что и у asort.

 Отправлено: 02.06.15 20:18. Заголовок: Pasha пишет: Если и..

Pasha пишет:

цитата:

Если интересно, могу поискать.

Павел это не эта тема случаем http://clipper.borda.ru/?1-0-0-00000475-000-10001-0-1276757268

 Отправлено: 02.06.15 22:10. Заголовок: Да, там есть эта фун..

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

 Отправлено: 02.06.15 22:31. Заголовок: Массив vs DB

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

 Отправлено: 02.06.15 23:01. Заголовок: petr707 пишет: масс..

petr707 пишет:

цитата:

массив загоняется во временную таблицу, можно hbmemio далее - INDEX или SORT - по вкусу, затем обратно - из DB-> в массив

Dima пишет:

цитата:

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

уже выше предлагалось.

 Отправлено: 03.06.15 11:11. Заголовок: Меня интересовало пр..

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

asort(), sort on и index on в самом Harbour.

Я полагал, что он от этого станет лучше.

Раз это невозможно, то вопрос исчерпан.

Благодарю за другие решения.