[?] asort() в Harbour

Форум » [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

Dima: subbota пишет: asort( ar, {|x,y| x[1] <= y[1] } ) asort( ar,,,{|x,y| x[1] < y[1] } )

subbota: Dima пишет: asort( ar,,,{|x,y| x[1] < y[1] } ) Да такое проходит, пробовал с Harbour 3.1 changlog v 16691 но при сравнении по знаку "<" правильй порядок в результате должен быть 1, 2, 4, 3 а не 1, 2, 3, 4 И не дело компенсировать ошибку функции ошибкой в прикладной программе А вот при компиляции с Harbour Version: 3.2.0dev Built on: 2015-05-20 замена "<=" на "<" уже и совсем не поможет Смотрел changlog, ф-ию asort() неоднократно дорабатывали, но по-видимому так и не довели до правильной. Может сообщить разработчикам

SergKis: subbota пишет:но при сравнении по знаку "<" правильй порядок в результате должен быть добавьте '11', '21' ... и опять нарушится символьное сравнение. Если Вы используете свой обработчик, так стройте правильный алгоритм его, например val(x[1]) < val(y[1]) или выравнивайте строки (если это важно) сдвигом вправо до определенной (одинаковой) длины а 3.2 еще в работе, мало ли что поменяют еще

Pasha: 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 Здесь просто неверно заданы параметры для asort. 2-й параметр - это номер начального элемента для сортировки. В этом случае он просто игнорируется, и выполняется обычная сортировка массива. Поскольку тип данных элемента - тоже массив, то сортировка не выполняется, и массив остается в первоначальном порядке. В asort вносятся небольшие улучшения, но это именно улучшения, а не исправления каких-то ошибок.

petr707: 1) лучше ar_rez := asort( ar,,,{|x,y| x[1] < y[1] } ) 2) ar[3,1]=ar[4,1]=11 - правило сортировки не выполняется, поэтому в результате - {.. ar[3] , ar[4]..} или {.. ar[4] , ar[3]..} - любой порядок из этих будет правильно выполненным результатом

subbota: Поясняю: Я привел два примера с ошибкой сортировки asort() двумерного массива. В обоих примерах массив сортируется по первому элементу подмассива. В первом примере этот элемент подмамассива числовой, а во втором - символьная строка. Разберу первый пример: 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] } ) -то потом при прохождении по массиву ar[] от начала к концу и выводе на экран вторых элементов подмассивов, то есть так: @ 3, 1 say ar[1,2] @ 4, 2 say ar[2,2] @ 5, 3 say ar[3,2] @ 6, 4 say ar[4,2] должны увидеть на экране цифры в порядке: 1, 2, 3, 4 другой порядок, в том числе: 1, 2, 4, 3 - указывает на ошибку сортировки. так как соседние элементы массива ar[] при сортировке должны меняться местами ТОЛЬКО в случае НЕВЫПОЛНЕНИЯ условия ar[ n, 1 ] <= ar[ n+1, 1 ] этому соответствует такой вызов функции: asort( ar,,, {|x,y| x[1] <= y[1] } ) Если же в условии сравнения заменить "<=" на "<" то при правильной работе asort() должны получить порядок вторых элементов: 1, 2, 4, 3 В случае практического применения это означает, что после сортировки массива с равными значениями ключей в двух соседних элементах по условию с "<=" , первым из них должен остаться тот, который и до сортировки был первым. Вот такая ф-ция сортирует правильно, но работает раз в 30 медленнее родной asort() function asort_my( ar, blk ) local i , ie := len( ar ) - 1, flag := .t. local z0 if ie > 1 do while flag flag := .f. for i := 1 to ie if ! eval( blk, ar[ i ], ar[ i+1 ] ) z0 := ar [ i ] ar[ i ] := ar[ i + 1 ] ar[ i + 1 ] := z0 flag := .t. endif next enddo endif return ar

Pasha: subbota пишет: этому соответствует такой вызов функции: asort( ar, {|x,y| x[1] <= y[1] } ) Вот фрагмент из описания функции ASORT: ASORT() Sort an array Syntax ASORT(<aTarget>, [<nStart>], [<nCount>], [<bOrder>]) --> aTarget Arguments <aTarget> is the array to sort. <nStart> is the first element of the sort. If not specified, the default starting position is one. <nCount> is the number of elements to sort. If not specified, all elements in the array beginning with the starting element are sorted. <bOrder> is an optional code block used to determine sorting order. If not specified, the default order is ascending. Параметр bOrder: {|x,y| x[1] <= y[1] } должен быть не вторым, а четвертым для функции ASORT. Если его указать вторым, то он будет проигнорирован. Т.е. надо указать не asort( ar, {|x,y| x[1] <= y[1] } ) а asort( ar,,, {|x,y| x[1] <= y[1] } )

subbota: Согласен с Pasha насчет местоположения блока кода в вызове asort() Примеры в постах исправил, но суть вопроса об ошибке в asort() осталась

subbota: Pasha пишет: надо указать не asort( ar, {|x,y| x[1] <= y[1] } ) а asort( ar,,, {|x,y| x[1] <= y[1] } ) Согласен с Pasha насчет местоположения блока кода в вызове asort() Примеры в постах исправил, но суть вопроса об ошибке в asort() осталась

petr707: Цитата ..так как соседние элементы массива ar[] при сортировке должны меняться местами А из чего такой вывод ? Должны - быть выстроены в итоге по правилу блока кода, но меняться местами - не обязательно, разве нет ? Похоже, что Вам требуется сортировка, где сравнения двух соседних значений недостаточно для определения порядка сортировки ? Например, номер элемента в первичном массиве.

Pasha: Если значения элементов одинаково, то результат выполнения a1[1] <= a2[1] будет равен .t. также a2[1] <= a1[1] тоже .t. В этом случае результат сортировки непредсказуем, он зависит, в каком порядке выполнялось сравнение элементов, так как сам блок кода не содержит точной информации о сравнении элементов. Можно предложить такую функцию для сортировки массива по одному или двум индексам: Function ASortA(a, n, n2) // ------------------------------------------------------------- // Сортирует двухмерный массив по индексу n // Если задан n2 - сортировка по двум индексам // ------------------------------------------------------------- Return ASort(a,,, if(n2 == nil,; {|x1, x2| x1[n] < x2[n]},; {|x1, x2| if(x1[n]=x2[n], x1[n2]<x2[n2], x1[n]<x2[n])} )) для сортировки в вашем случае надо вызвать: ASORTA(aArray, 1, 2) но опять таки, сортировка будет выполняться не по исходному порядку, а по значению 2-го подэлемента

subbota: Pasha пишет: В этом случае результат сортировки непредсказуем Не соглашусь с этим замечанием. В случае когда ключевые значения одинаковы элементы не должны меняться местами. Вот еще готовый пример. Из него видно, что из asort(), index on и sort on правильно работает только index on ( а при правильной работе все они должны давать одинаковый результат ) Пример: private dim := {} * По первому элементу подмассива будет сортировка или индексирование * Во втором элементе подмассива записан * правильный порядковый номер после сортировки или индексирования aadd( dim, { 11, "2" } ) aadd( dim, { 1, "1" } ) aadd( dim, { 12, "3" } ) aadd( dim, { 12, "4" } ) private struct := {} aadd( struct, { "p1", "N", 2, 0 } ) aadd( struct, { "p2", "C", 2, 0 } ) dbcreate( "arr", struct ) use arr.dbf private i for i := 1 to len( dim ) dbappend( ) arr->p1 := dim[i,1] arr->p2 := dim[i,2] next sort on p1 to arsrt.dbf index on p1 to arr asort( dim,,, { |z1,z2| z1[1] <= z2[1] } ) use arsrt new private b1 := "", b2 := "", b3 := "" for i := 1 to len( dim ) b1 += dim[i,2] + " " b2 += arr->p2 b3 += arsrt->p2 arr->( dbskip() ) arsrt->( dbskip() ) next close arr close arsrt clear screen @ 1,0 say " После asort() получен порядок: " + b1 // 1 2 4 3 @ 3,0 say " После index on получен порядок: " + b2 // 1 2 3 4 - правильно @ 5,0 say " После sort on получен порядок: " + b3 // 1 2 4 3 inkey(0)

petr707: Цитата..они должны ..не должны ..правильно По формальной логике, такие утверждения должны быть аргументированы, то есть должны ссылаться на какое-либо правило. В Вашем тексте таких ссылок не обнаружено.

Pasha: subbota пишет: Но asort() ошибается еще более грубо. ... asort( dim, { |z1,z2| z1[1] <= z2[1] } ) Как можно что-то говорить о работе asort, если опять передать этой функции неправильный параметр ? Насчет остального: результат сортировки полностью определяется условием сортировки. В условии сортировки нет никакого первичного номера элемента. Следовательно, все три режима работают правильно (если, конечно, для asort наконец-то указать правильный параметр). Различия в результате объясняются неопределенностью условия сортировки, поскольку алгоритмы сортировки не являются полностью идентичными.

subbota: Проверил то же самое в Clipper 5.2e результат такой После asort() получен порядок: 1 2 4 3 После index on получен порядок: 1 2 3 4 - правильно После sort on получен порядок: 1 2 3 4 - правильно

subbota: Pasha пишет: Как можно что-то говорить о работе asort, если опять передать этой функции неправильный параметр ? Извиняюсь по поводу повторной ошибки в месте параметра условия сортировки. Опять исправил свой пост. Понимаю объяснение насчет неидентичности алгоритмов, но не соглашаюсь с тем что без явного указания в условии сортировки первоначального положения элемента, элементы, имеющие одинаковое значение ключа, в результирующем массиве будут занимать места относительно друг-друга отличающиеся от первоначальных. Это все-таки существенная недоработка asort() и если разработчики ее устранят, то в Harbour будет одним подводным камнем меньше. То же и про sort on. Замена index on на sort on и на asort() не должна провоцировать получения неидентичных резудьтатов. *---- Я об этот подводный камень споткнулся впервые давно на Clipper. Но тогда не докопался до сути. Думаю, что об него споткнуться еще многие.

petr707: Можно не искать нужный сложный алгоритм.. Просто измените входные данные так, чтобы в принципе не было совпадающих значений при сортировке, например сортируйте не по 1 элементу массива, а по 3-му - он только для сортировки, и его значение, к примеру ar[n,3] := str(ar[n,1),10] +str(n,5) При равенстве значений ar[n,1] - будет учтен порядковый номер в массиве.

Dima: local ar := {} cls 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 wait Clipper 5.2e Результат 1 2 4 3

SergKis: все правильно, не до конца продуман обработчик для asort и для {11,'3'}, {11,'4'} перестановки не являются нарушением условия и претензий к asort не принимаются, мое мнение. Пишите правильный обработчик.

Dima: SergKis пишет: Пишите правильный обработчик. +1

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. Я полагал, что он от этого станет лучше. Раз это невозможно, то вопрос исчерпан. Благодарю за другие решения.

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