Очень сложная задачка на сортировку массива списков значений. #6080

Есть массив списков значений, представляют собой Таблицу значений. Если сортировать допустим строки по первому столбцу(СписЗн[1]), то как оптимальней синхронизировать записи (значения остальных СЗ чтоб соотвествовали записям отсортированного списка)

Я так понял таблица все равно двухмерная?

СЗ - это слолбец. Массив СЗ - получается что-то типа ТЗ. Все СЗ естественно одинакового размера.

А не проще в ТЗ все хранить?

Объекта ТЗ нет вообще, массив СЗ заменяет его. Многие методы ТЗ массивом СЗ описаны. Осталось несколько проблемных, одна из проблем - сортировка.

Создать еще один СЗ с содержимым: 1 2 3 4 5 6 ... То есть номера записи остальных СЗ. И в процессе сортировки сортировать его, а потом получать значения из других СЗ по номеру записи. Как такое решение (через жопу правда, но такая и задача в принципе...)

Блин, тока щас дошло... Да это-ж аналог индексного файла ;))

5. Это слишком медленно.

По-моему все просто? При смене двух соседних элементов массива (непременное действие при сортировке) менять местами не только их, но и делать то же самое для всех остальных массивов. Например, есть ЯЯ хх зз АА 11 22 Сортируя по первой колонке, мы меняем местами не только ЯЯ и АА, но и хх и 11, а также зз и 22, то есть и попарно обмениваем значения для всех остальных колонок.

8. Все верно, но сортируя один СЗ, мы должны запомнить соотвествия остальных значений других СЗ сортируемым значениям. Затем путем перебора изменить позиции значений для соотвествия сортированным. Это долго. Медленней, чем штатный метод "Сортировать" ТЗ.

А что же мешает синхронно все пары элементов в двух строках менять местами (сравнивая, однако, только два значения в первой колонке)? Я не понял, в чем тут трудность - по-моему все так делают... Сортировка по двум и более колонкам аналогично, но надо производить не одно, а от 1 до N сравнений, пока не натолкнетесь на различие (одинаковые значения вверху и внизу не считаются). N- число сортируемых колонок.

10. Представь: две колонки (Разм(СЗ)=2), каждая колонка - это список значений. Чтобы отсортировать делаю так СЗ[1].Сортировать. Теперь нужно Сз[2] - значения поставить на новые позиции, которые стали у значений Сз[1]. Можно зашить индекс в представление и по индексу, путем перебора, изменить позиции значений СЗ[2] таким образом, чтобы представления СЗ[1]=представлениям Cз[2]. Но это слишком медленно. Возможно есть более оптимальные варианты. Их и ищу.

имхо не надо никаких Сортировать!!! Сканируйте список и обменивайте местами значения (точнее, строки) попарно. Алгоритмы, в т.ч. quicksort, везде описаны. Сэкономить на этом не удастся - надо его и написать.

12. Идея понятна, спасибо, но если будет к примеру 20 столбцов и 50000 строк - то процесс может затянуться на минуты.

а это без разницы - скорость сравнения двух строк в зависимости от числа сравниваемых столбцов растет даже не линейно, а в среднем вполовину меньше (вроде бы так). А вот зависимость от числа строк более ощутима, но для алгоритма quicksort зависимость наиболее "пологая" (но он жрет много памяти в стеке).

14. Спасибо за идею. На досуге поюзаю.

2Матрейя Я так понимаю это для реализации ТЗ в 2С. Только почему СЗ у тебя это колонка, не проще было бы его строкой сделать. У тебя: ССССС ЗЗЗЗЗ Предлагаю: СЗ СЗ СЗ Тогда и сортировка построчная проще и быстрее.

(Матрейя) ИМХО: Я уже об этом думал тоже, но скажу одно. ТЗ нужно реализовывать на 0 уровне ... иначе по скорости обработке она будет уступать стандартной 1с ...

Полностью согласен с , если писать на уровне 2 будет тормознуто.

и ваще собачка чего то конкретно тупит....

(17, 18) А как быть с объектами, которые создаются на 1 и 2 уровнях. Как их в ТЗ записывать, ведь 0 уровень ничего не знает о 1 и 2.

По принципу СпискаЗначений, ведь он как то сделан и работает ...

А зачем объекту уровня 0 знать что-то об остальных уровнях? Он предоставляет свои свойства и методы, объекты других уровней ими пользуются.

romix Я просто... Такое впечатление, что просто детсадовец... Сложность алгоритма Эн Логарифмов Эн... и всё!!! На сомом деле - быстрее будет создать ТЗ из двух колонок... Номерстрок, и представление, отсортировать - и грузануть обратно в массив... Рекурсия легко заменяется стеком - рекурсия в 1С очень медленная...

Речь идет о платформе 2С от vtools.ru. Непонятно, почему ТЗ не включат в уровень ядра 2С; видимо, со временем в порядке оптимизации это сделают. Еще быстрее алгоритмы сортировки не "на месте", а в другой массив. Ваш алгоритм с двумя колонками я не понял. Возможно, он слишком сложен.

(+24) .. или не работоспособен. "Грузануть обратно в массив" - а как быть с остальными колонками?? Рекурсия как вы думаете за счет чего сделана? Она и сделана при помощи стека.

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

Насчет рекурсии - сделайте пожалуйста факторпиал при помощ рекурсии и без - и сравните результаты... Либо алгоритм закраски - рекурсивный и на стеке... а если не можете - Х_У_Л_И П_И_З_Д_Е_Т_Ь??? А если можете - результаты замсера в студии... Я приводил пример рюкзака -  80% времени рекурсивный вызов... на стеке - в 4-5 раз быстрее.

Я не прав, что рекурсия сама сделана на стеке? Извините, но она СДЕЛАНА на стеке, откройте любой учебник. То, что она медленнее (особенно в интерпретаторах) - очень даже может быть. То, что нужно использовать не ее, а другой алгоритм (чем плох со вторым массивом?) - очень может быть. Не забывайте, что речь идет о системе 2С, и код там всегда могут "втупую" перенести в компилятор, где ограничения рекурсии не так существенны по сравнению с интерпретатором. Грубо говоря, один рекурсивный вызов означает добавочные команды  add sp, ноль и более команд push под параметры и лишний call/ret (в современных процах все по 1 такту и менее). В интерпретаторах же это означает очень медленный вызов malloc на каждую итерацию рекурсии.

(+28) со вторым массивом = я хотел сказать, двумя таблицами, из одной копировать отсортированные строки в другую. Да как угодно можно. Рекурсия проще понимается - хотя расписать ее как итерационный алгоритм (для оптимизации) тоже можно. Или извернуться с дополнительной памятью - чем больше - тем быстрее работает. Идеальный случай сортировки описал Крис Касперски, когда нужно 0 сравнений (но очень много памяти).

Извиняюсь за грубость - нервы не в порядке... Насчет того, что рекурсия сделана на стеке - ежу понятно - я имел в виду - очень большие тормоза при работе с ней в 1С - то есть - имеет смысл её использовать только если в теле рек. процедуры - трудоемкие вычисления. Насчет 2С - Делается двва паралельных массива - и сортируются паралельно - да и всех делов... Как я сказал на Кубани - куча методов - Слияния отрезков, Квик-сорт, Корпоративная (по бинарному дереву) - всё дается в интститутах. и всё за эн логарифмов.

30. Всего делов то приводят тому, что скорость сортировки самописной ТЗ больше скорости сортировки ТЗ 1с. И это несмотря на быстрый интерпретатор 2с. Речь идет не о том, что я не знаю как, а о том, что у меня не получается быстрее. Romix: пришла идея ТЗ сделать на основе временной таблицы SQL. ИМХО, это самый лучший (быстродействие, большие возможности по дополнительным нестандартным методам) вариант (кроме конечно объекта уровня 0).

Ну да, есть в MySQL такие таблицы - которые только в памяти... Чем не ТЗ? :-) Еще и селектить из нее можно быстро... А что, 2С разве позволяет в уровне 1 юзать все возможности MySQL?

(+32) А свертку (следующий шаг) там делать как? :-) А, хотя наверное можно фетчить отсортированный запрос в массив, переходя на новую строку только при несовпадении измерений свертки...

32. Насчет всех возможностей не знаю, но разницы не заметил: можно  записывать, обновлять данные, работать с формой одинаково что в конфигураторе на уровне объектов 1 уровня, что в Предприятии2С. 33. Select and Group by and Into NewTempTable

Я похоже тормознул - а ведь работа с ТЗ в этом случае будет по сети? А связь по сети не всегда имеет широкий канал... Идеология SQL-как можно меньше юзать сеть...

Мне тут на выходных пришли две мысли: - использовать вторую ТЗ (СЗ) как индекс, причем ТЗ предпочтительнее (индекс сложный можно создать), индекс понадобится при обходе (выборке) отсортированной ТЗ; - использовать в качестве ТЗ временную таблицу на SQL сервере. Более подходящий - первый вариант, мне кажется нерациональным привязывать такой универсальный объект как ТЗ к конкретному SQL серверу. Да и сеть будет нагружаться, ведь в 1С такие объекты как ТЗ и СЗ находятся на локальной машине.

36. В случае временной таблицы SQL - ТЗ будет обрабатываться на сервере. На клиентскую машину - только окончательный результат запроса.

Ага, после сортировки результат - ВСЯ таблица. Хотя... Все ж думаю им (vtools) надо ТЗ в 0-уровень запихнуть или тем, кто пишет на 1 уровне использовать временную таблицу на сервере.

38. ТЗ на первом уровне на базе временной таблицы MSSQL - нормально реализуется.  SQLLite - что-то я не победил :(.  В MSSQL - временные таблицы хранятся в базе tempdb, отдельные экземляры для каждого процесса... SQLLite - создание успешно, но потом этой временной таблицы как бы нет. :(

Я, к сожалению, только в MS SQL работаю

Приведи замеры... Разница не такая уж и большая... Все дело в том, что самая трудоемкая операция - добавление/изменение значения в ТЗ... В этот момент строится индекс. А сортировка по индексу - уже эн... только добавление - логарифм, а нужно добавить эн элементов. Приведи пример с замером скорости.

41. Добавление числовых значений по 3 столбцам и 50000 строкам: 2. ТЗ на массивах 2с - 18сек 3. Тз на списках значений 2с - 3сек.