Подумывал тут пойти по деревьям на языке М – есть концептульный вопрос.

kvasov
Дата: 02.08.2005 18:25:40
Подумывал тут пойти по деревьям на языке М – есть концептульный вопрос.

1. Можно в узлах глобала хранить данные в виде списков, с последующим выбором элементов списка List-функциями.

2. А можно от списков вообще отказаться, а элементы данных хранить прямо узлами с многомерными индексами в простом «одноэлементном» виде.


Какой вариант лучше и насколько существенно, с точки зрения скорости выборки /места хранения на диске и пр. ?
Maksim UM
Дата: 02.08.2005 18:46:02
Очень зависит от задачи.
У списка преимущество в атомарности
(либо записалось все, либо ничего).
Пожалуй списки компактнее и быстрее,
если не очень большой список.
kvasov
Дата: 03.08.2005 11:16:45
Прочитал тут в книжке:

---- Прежде чем Cache записывает глобальную переменную, отдельные индексы обьединяются в одну символьную строку. Таким образом, из трехуровнего индекса глобала ^OTD.Tovar(123000,”XL”, “синий”) получается сохраняемая строка символов
OTD.Tovar|123000|XL|синий. Отсюда вытекает, что скорость доступа к индексированным переменным не зависит от числа индексов.


То есть списки всюду.
А если список длинной 3 киллометра и нужен 250-ый элемент, cache начинает что ли сканировать с первого байта и ищет 250 разделителей элементов, чтобы потом считать 250-ый элемент?
ну я
Дата: 03.08.2005 15:41:09
Одно дело - значения ключей, другое дело - список который записан в узле.
Если список длинный (тот, который $lb()), то для взятия N элемента пробегается весь список последовательно. Если это критично то используйте хранение в фиксированном формате, и стройте доступ на $extract. В списке не используются разделители - это тего-организованная структура - в начале каждого элемента списка стоит индикатор сколько места на него отводится.
MX--ALEX
Дата: 03.08.2005 17:00:33
ну я
Одно дело - значения ключей, другое дело - список который записан в узле.
Если список длинный (тот, который $lb()), то для взятия N элемента пробегается весь список последовательно. Если это критично то используйте хранение в фиксированном формате, и стройте доступ на $extract. В списке не используются разделители - это тего-организованная структура - в начале каждого элемента списка стоит индикатор сколько места на него отводится.


zxxxxxASDFGHHJKLQWETTYUOPIOPOOP

z-длина списка указателей xxxxx
x-координата начала каждого элемента списка (разделителей нет)

было бы обращение к нужному элементу всегда в 3 счета
независимо от длины списка

почему они так не сделали?
ну я
Дата: 04.08.2005 11:03:31
Конечно я не знаю "почему они" делают так или не так.

Но предложенный вариант тоже можно покритиковать.
1) В приведенном варианте нет информации о длине элемента. Сколько байт брать?
2) Если изменилась длина поля №2, а всего полей N, то сколько указателей понадобится пересчитать если поля предполагается хранить с переменной длиной? Если длина полей фиксирована то зачем вести список указателей на начало?
3) Тегоориентированная структура $lb() имеет преимущество в том, что можно сконкатенировать два списка как последовательность байт и получим новый корректный список.
4) В списках $lb() присутствует упаковка числовых величин.

Идеи с предложениями эффективных структур хранения мне нравятся, готов обсуждать.
MX--ALEX
Дата: 04.08.2005 13:21:01
1) В приведенном варианте нет информации о длине элемента. Сколько байт брать?
--- разница между двумя x - этим и следующим (для последего - с общей длиной )

2) Если изменилась длина поля №2, а всего полей N, то сколько указателей понадобится пересчитать если поля предполагается хранить с переменной длиной?
--- в среднем половину - но меняется на порядки реже чем считывается
если это база данных

3) Тегоориентированная структура $lb() имеет преимущество в том, что можно сконкатенировать два списка как последовательность байт и получим новый корректный список.
--- очень на практике редкая операция

4) В списках $lb() присутствует упаковка числовых величин.
--- не нужно паковать - больше мороки
kvasov
Дата: 05.08.2005 11:31:07
Правильно ли я понял, что преимущество хранения информации в самих индексах глобала перед списками в качестве значений узла глобала в том, что глобал всегда сортируется по своим индексам и это оптимизирует $Order–выборки, а если ты запечатал инфу в список, то для какой либо оптимизации выборки инфы из списка, которая там уже никак не отсортирована, ты уже должен создавать 1) обьекты 2) и только эти обьекты умеют создавать отдельные индексные файлы, которые позволяют сортировать инфу, хранящуюся в списках?

А индексные файлы – это кусок технологии обьектов, и если ты отказался от обьектов, то забудь и про эти индексные файлы?

И вывод как-бы такой – где оптимизируешь быструю выборку – надо сохранять инфу в индексах глобала (которые автосортируются), а не в списках (сортировка в которых уже невозможна без обьектов), а сами обьекты – это по большому счету уже проигрышь в производительности, если задача может решаться без них.
ну я
Дата: 05.08.2005 12:29:07
MX--ALEX
1) В приведенном варианте нет информации о длине элемента. Сколько байт брать?
--- разница между двумя x - этим и следующим (для последего - с общей длиной )

2) Если изменилась длина поля №2, а всего полей N, то сколько указателей понадобится пересчитать если поля предполагается хранить с переменной длиной?
--- в среднем половину - но меняется на порядки реже чем считывается
если это база данных


Что интересно - похожую структуру (не в точности, но очень похожую) применяет mssql2000 для строк. Именно в такой предварительной служебной структуре строки хранится инфа про размещение строк varchar и nvarchar

MX--ALEX
3) Тегоориентированная структура $lb() имеет преимущество в том, что можно сконкатенировать два списка как последовательность байт и получим новый корректный список.
--- очень на практике редкая операция

4) В списках $lb() присутствует упаковка числовых величин.
--- не нужно паковать - больше мороки


Остается предположить, что у разработчиков приоритеты были другими. Кстати, о паковке - это немаловажно - чем компактнее хранятся данные тем меньше дисковых операций. Учитывая, что дисковые операции в очень много раз дороже процессорных (по времени), вполне имеет смысл пойти на решение алгоритмических проблем.
MX--ALEX
Дата: 05.08.2005 15:25:12
kvasov
Правильно ли я понял, что преимущество хранения информации в самих индексах глобала перед списками в качестве значений узла глобала в том, что глобал всегда сортируется по своим индексам и это оптимизирует $Order–выборки, а если ты запечатал инфу в список, то для какой либо оптимизации выборки инфы из списка, которая там уже никак не отсортирована, ты уже должен создавать 1) обьекты 2) и только эти обьекты умеют создавать отдельные индексные файлы, которые позволяют сортировать инфу, хранящуюся в списках?

А индексные файлы – это кусок технологии обьектов, и если ты отказался от обьектов, то забудь и про эти индексные файлы?

И вывод как-бы такой – где оптимизируешь быструю выборку – надо сохранять инфу в индексах глобала (которые автосортируются), а не в списках (сортировка в которых уже невозможна без обьектов), а сами обьекты – это по большому счету уже проигрышь в производительности, если задача может решаться без них.


у нас вся система (уровня 1с-предприятие)
построена на глобалах без обьектов (обьекты не используем в целях
совместимости MSM - CACHE - M3-LITE )
т е сортировать и создавать индексн глобалы можно и без обьектов
списки используем только по $p() - тоже для совместимости
все работает быстро даже на крупных обьектах