The sort algorithm is not stable

вот в чем проблема основная

ну по крайней мере видно теперь, где проблема

Я про это тебе говорил прямым текстом :< table.sort — это quiksort. Его отличительная особенность как раз то, что он в среднем быстр, но выдаёт произвольный порядок одинаковых значений

ага, осталось найти нормальный вариант merge sort или самому написать

не могу найти готового модуля вроде cjson

было бы здорово, если бы такое было

Rosetta code

там нестабильный алгоритм на луа, ну по крайней мере что я нашел

Там много алгоритмов. Кстати, merge, помнится, тоже нестабильный. Пузырьки давай. Или гномов. Ты что, не справишься с пузырьками?

https://en.wikipedia.org/wiki/Sorting_algorithm#Stability

ну да, видимо придется другой взять, т.к. на розетта коде хороший код

просто странно что мерж сорт там указан как стабильный

Я могу путать. Энивей, ты возишься с сортировкой уже полтора-два часа, хотя мог бы написать bubble за пять минут : )

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

(a bubble — всего за пять минуточек, ибо тупая как три копейки)

просто ищу лучший и самый оптимальный способ

до 1000

О да. И сложность On в лучшем случае!

но таких сортировок много может быть

одновременных в смысле в нгинксе

до 1000

Ой, ты сэкономишь пятьсот процессорных тактов.

ну хочется оптимально сделать т.к. нагрузка большая

ну хочется оптимально сделать т.к. нагрузка большая

Ты сначала сделай как сделается, и напиши бенчмарки. Посмотри как на реальных данных получается.

ну хочется оптимально сделать т.к. нагрузка большая

Ты знаешь что такое бинарный поиск?

ну дробить массив на части?

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

ну дробить массив на части?

Ну типа. Это когда тебе надо найти элемент условно больше/меньше определённого значения. Как игра "больше-меньше". Делишь массив пополам, смотришь, искомое должно быть больше или меньше центрального. Потом смотришь ту половину, в которой находится искомое, точно так же делишь пополам и т.п.

Это - самый эффективный способ поиска в сортированных больших данных, из не требующих дополнительной памяти.

буду сейчас разбираться, спасибо. я медленно разбираюсь т.к. по сути с этим дела никогда толком и не имел.

но хочу сделать хорошо, максимально оптимально

Но только вот ведь незадача: на малых данных (условно до 50 элементов) — он менее эффективен обычного перебора значений, так как требует делений. Поэтому тупой перебор оказывается быстрее.

в среднем - 200-300 значений

Я тебе не про то. Экстраполируй мои слова на свою задачу.

да, я понял идею

т.е. возможно и не нужно использовать супер алгоритм т.к. на малом количестве значения он будет даже хуже

Ты в курсе что в некоторых условиях, bubble оказывается быстрее и круче quiksort'а? (когда массив почти отсортирован, например, хотя гномы тут ещё круче), и не требует доп-памяти? Карочи, не совокупляй себе и окружающим моск, сделай сначала так чтобы работало, улучшать будешь как понадобится. Предварительные оптимизации == плохо.

угу, спасибо, буду пробовать

В Lua есть налог printf как например: в Ruby puts "The number is %d" % [5], или string intepolation как в Ruby и JS: p "Number #{2+2}" console.log(' Number ${2+2}')?

string.format

string.format

спасибо

Входить в новый язык интересно, новый мир, свои акронимы, например PiL => Programming in Lua

спасибо

Что пилить собираешься, если не секрет?

Что пилить собираешься, если не секрет?

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

с jit и ffi он ещё быстрее

с jit и ffi он ещё быстрее

про jit я в курсе, а вот что такое ffi буду сейчас гуглить.

ясно вызов модулей из C

ffi это ssh, когда по клавиатуре сильно промахнулся

https://habr.com/ru/post/113804/

https://habr.com/ru/post/113804/

спасибо

с jit и ffi он ещё быстрее

c ffi он частенько с утечками памяти )

это уже проблема в программисте

я думаю это сам ффи не особо хорошо работает, хотя могу и ошибаться

почти любой модуль будет вызывать утечки, такое ощущение по крайней мере

https://habr.com/ru/post/113804/

В прошлый раз я сравнивал LuaJIT 2.0 Beta 5 и JavaScript в различных браузерах а как автор статьи LUA добавил в браузеры?

например так https://github.com/technix/instead-playground

но вряд ли автор статьи именно это имел в виду

но вряд ли автор статьи именно это имел в виду

мне еще интересно что он обозрачил как RPS - requests per second для серверов в данном контексте явно не катит.

скорее он сравнивал работу жса в браузере и луы в интерпретаторе

скорее всего брал наиболее свежие интерпретатор и браузер

на тот момент

но суп не в этом

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

помнится, мне баили, что и жс умеет в jit

Есть ли способ в Lua посомтреть массив также как в Ruby p array?

какой-то инстурмент быстрой оценки что лежит в таблице

итераторами только наверно

мне кажется в случае использования на сайтах луа выигрывает по той причине, что не нужен коннект на соккет, поэтому и работает быстро

хотя, в метатаблицу можно наверно зарядить способ поинтереснее

https://habr.com/ru/post/346892/

https://habr.com/ru/post/346892/

спасибо

Это Снусу спасибо, он автор.

Вот ещё http://computercraft.ru/topic/1090-metatablitsy-lua/

добротная статья

и Снусу спасибо тоже.

да, он крутой

я кстати вчера в итоге сделал сортировку стабильную, причем использовал table.sort-таки

реализовал и пузырьковый вариант и инсершен вариант, правда не потестировал еще, но думаю вариант с table.sort будет самым лучшим

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

Сишные структуры можно точно так же чистить сборщиком мусора, если что. Когда они перестают быть нужны с луёвой стороны — освобождать память.

а есть какая-нибудь статья, как это правильно делать?