Отправлено: 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

 Отправлено: 27.05.15 12:01. Заголовок: subbota пишет: asor..

subbota пишет:

цитата:

asort( ar, {|x,y| x[1] <= y[1] } )

asort( ar,,,{|x,y| x[1] < y[1] } )

 Отправлено: 28.05.15 10:23. Заголовок: Dima пишет: asort( ..

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() неоднократно дорабатывали, но по-видимому так и не довели до правильной.

Может сообщить разработчикам

 Отправлено: 28.05.15 11:17. Заголовок: subbota пишет:но при..

subbota пишет:

цитата:

но при сравнении по знаку "<" правильй порядок в результате должен быть

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

 Отправлено: 28.05.15 11:57. Заголовок: asort( ar, {|x,..

цитата:

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 вносятся небольшие улучшения, но это именно улучшения, а не исправления каких-то ошибок.

 Отправлено: 28.05.15 13:43. Заголовок: asort

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]..}
- любой порядок из этих будет правильно выполненным результатом

 Отправлено: 28.05.15 18:08. Заголовок: Поясняю: Я привел дв..

Поясняю:
Я привел два примера с ошибкой сортировки 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

 Отправлено: 28.05.15 18:21. Заголовок: subbota пишет: этом..

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] } )

 Отправлено: 28.05.15 18:42. Заголовок: Согласен с Pasha нас..

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

 Отправлено: 28.05.15 18:47. Заголовок: Pasha пишет: надо у..

Pasha пишет:

цитата:

надо указать не asort( ar, {|x,y| x[1] <= y[1] } ) а asort( ar,,, {|x,y| x[1] <= y[1] } )

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

 Отправлено: 28.05.15 20:09. Заголовок: asort

Цитата ..так как соседние элементы массива ar[] при сортировке должны меняться местами

А из чего такой вывод ?
Должны - быть выстроены в итоге по правилу блока кода, но меняться местами - не обязательно, разве нет ?

Похоже, что Вам требуется сортировка, где сравнения двух соседних значений недостаточно для определения порядка сортировки ?
Например, номер элемента в первичном массиве.

 Отправлено: 29.05.15 08:53. Заголовок: Если значения элемен..

Если значения элементов одинаково, то результат выполнения

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-го подэлемента

 Отправлено: 29.05.15 11:08. Заголовок: Pasha пишет: В этом..

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)

 Отправлено: 29.05.15 13:02. Заголовок: asort

Цитата..они должны ..не должны ..правильно

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

В Вашем тексте таких ссылок не обнаружено.

 Отправлено: 29.05.15 17:29. Заголовок: subbota пишет: Но a..

subbota пишет:

цитата:

Но asort() ошибается еще более грубо. ... asort( dim, { |z1,z2| z1[1] <= z2[1] } )

Как можно что-то говорить о работе asort, если опять передать этой функции неправильный параметр ?
Насчет остального: результат сортировки полностью определяется условием сортировки. В условии сортировки нет никакого первичного номера элемента. Следовательно, все три режима работают правильно (если, конечно, для asort наконец-то указать правильный параметр). Различия в результате объясняются неопределенностью условия сортировки, поскольку алгоритмы сортировки не являются полностью идентичными.

 Отправлено: 29.05.15 17:39. Заголовок: Проверил то же самое..

Проверил то же самое в Clipper 5.2e
результат такой

После asort() получен порядок: 1 2 4 3

После index on получен порядок: 1 2 3 4 - правильно

После sort on получен порядок: 1 2 3 4 - правильно

 Отправлено: 29.05.15 18:36. Заголовок: Pasha пишет: Как мо..

Pasha пишет:

цитата:

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

Извиняюсь по поводу повторной ошибки в месте параметра условия сортировки.
Опять исправил свой пост.

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

Это все-таки существенная недоработка asort() и если разработчики ее устранят,
то в Harbour будет одним подводным камнем меньше.
То же и про sort on.
Замена index on на sort on и на asort() не должна провоцировать получения неидентичных резудьтатов.

*----
Я об этот подводный камень споткнулся впервые давно на Clipper. Но тогда не докопался до сути.
Думаю, что об него споткнуться еще многие.

 Отправлено: 29.05.15 18:49. Заголовок: А если иначе..

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

 Отправлено: 29.05.15 19:14. Заголовок: local ar := {} cls a..

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

 Отправлено: 29.05.15 20:49. Заголовок: все правильно, не до..

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

 Отправлено: 29.05.15 20:53. Заголовок: SergKis пишет: Пиши..

SergKis пишет:

цитата:

Пишите правильный обработчик.

+1

 Отправлено: 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.

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

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

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