Переключение на Главную Страницу Страницы: [1] 2  ОтправитьПечать
Очень популярная тема (более 25 ответов) ИТЗ: порядок и индексирование (число прочтений - 9881 )
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
ИТЗ: порядок и индексирование
13. Декабря 2007 :: 09:32
Печать  
При построении индекса и выборе строк по этому индексу происходит "пересортировка" строк.
Пример:
Код
Выбрать все
Процедура Сформировать()
	стрИмя="Имя";
	ИТЗ=СоздатьОбъект("ИндексированнаяТаблица");
	ИТЗ.НоваяКолонка(стрИмя);

	ИТЗ.НоваяСтрока();
	ИТЗ.Имя = "Петров";
	ИТЗ.НоваяСтрока();
	ИТЗ.Имя = "Иванов";
	Сообщить("После заполнения: "); й=0;
	ИТЗ.ВыбратьСтроки();
	Пока ИТЗ.ПолучитьСтроку() = 1 Цикл
		й=й+1; Сообщить(""+й+". "+ИТЗ.Имя);
	КонецЦикла;

	Сообщить("После создания индекса: "); й=0;
	ИТЗ.ДобавитьИндекс(стрИмя,стрИмя);
	ИТЗ.ВыбратьСтроки(стрИмя);
	Пока ИТЗ.ПолучитьСтроку(стрИмя) = 1 Цикл
		й=й+1; Сообщить(""+й+". "+ИТЗ.Имя);
	КонецЦикла;
КонецПроцедуры 


В строке сообщения видим:
Цитата:
После заполнения:
1. Петров
2. Иванов
После создания индекса:
1. Иванов
2. Петров

Мне нужен именно тот порядок, который существует в основном индексе. Как с этим можно бороться?
  
Наверх
 
IP записан
 
kms
1c++ power user
1c++ moderator
Отсутствует


я хочу, чтоб сюда проложили
дорогу оттуда...

Сообщений: 4632
Зарегистрирован: 19. Мая 2006
Re: ИТЗ: порядок и индексирование
Ответ #1 - 13. Декабря 2007 :: 09:59
Печать  
JohnyDeath писал(а) 13. Декабря 2007 :: 09:32:
Мне нужен именно тот порядок, который существует в основном индексе. Как с этим можно бороться?

Зачем тогда индекс?
  

De quelle planète es-tu?
Наверх
 
IP записан
 
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: ИТЗ: порядок и индексирование
Ответ #2 - 13. Декабря 2007 :: 10:16
Печать  
Ну это упрощенный пример. В своей задаче я строю индекс с установленным флагом уникальности, чтобы определить список уникальных значений и именно в том порядке, который идёт в основном индексе. Т.е. у меня есть таблица:
Цитата:
1. Петров
2. Иванов
3. Иванов
4. Петров
5. Петров
6. Иванов

Хочу получить список, состоящий из элеменотв "Петров" и "Иванов", и именно в том порядке, в котором они впервые встречаются в ИТЗ. Реально?
  
Наверх
 
IP записан
 
kms
1c++ power user
1c++ moderator
Отсутствует


я хочу, чтоб сюда проложили
дорогу оттуда...

Сообщений: 4632
Зарегистрирован: 19. Мая 2006
Re: ИТЗ: порядок и индексирование
Ответ #3 - 13. Декабря 2007 :: 10:37
Печать  
В логике засада здесь начинается раньше, чем ты думаешь.
При построении уникального индекса для строки "Петров" ты можешь получить в результат любую строку из (1, 4, 5).
Т.е., построив уникальный индекс, ты потерял информацию о расположении строки.

То, что ты хочешь сделать - сделать можно.
Например, построив 2 индекса: уникальный и неуникальный.

Для каждого вхождения в уникальный индекс ищем первую строку с тем же ключем в неуникальном (определяем ее номер строки).
Номер строки и значение сохраняем во временной таблице.

После заполнения, строим новый индекс по временной таблице - по колонке с исходными номерами строк.

Итого: 3 индекса и 1 временная таблица.
Ну, не факт, что нельзя сделать лучше, но это уже думать надо.
  

De quelle planète es-tu?
Наверх
 
IP записан
 
kms
1c++ power user
1c++ moderator
Отсутствует


я хочу, чтоб сюда проложили
дорогу оттуда...

Сообщений: 4632
Зарегистрирован: 19. Мая 2006
Re: ИТЗ: порядок и индексирование
Ответ #4 - 13. Декабря 2007 :: 10:49
Печать  
+
Лирика:

Кстати, как раз для таких случаев, в свое время была добавлена возможность уникального обхода неуникального индекса.
Т.е. в теории достаточно одного индекса в исходной таблице.

На практике проблема в том, что итерировать по одному индексу в двух независимых выборках сейчас невозможно (или крайне неудобно).
Именно отсюда и появилось предложение в роадмапе по выделению итераторов в отдельные боевые единицы.
  

De quelle planète es-tu?
Наверх
 
IP записан
 
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: ИТЗ: порядок и индексирование
Ответ #5 - 13. Декабря 2007 :: 11:05
Печать  
Не, Миш, тут дело даже не в уникальности индекса, т.е. если даже сделать заполнение ИТЗ из 0-го поста так:
Код
Выбрать все
ИТЗ.НоваяСтрока();
	ИТЗ.Имя = "Петров";
	ИТЗ.НоваяСтрока();
	ИТЗ.Имя = "Иванов";
	ИТЗ.НоваяСтрока();
	ИТЗ.Имя = "Иванов";
	ИТЗ.НоваяСтрока();
	ИТЗ.Имя = "Петров";
	ИТЗ.НоваяСтрока();
	ИТЗ.Имя = "Петров";
	ИТЗ.НоваяСтрока();
	ИТЗ.Имя = "Иванов"; 


ничего более не меняя (остается обыкновенный НЕуникальный индекс), получаем следующее:
Цитата:
После заполнения:
1. Петров
2. Иванов
3. Иванов
4. Петров
5. Петров
6. Иванов
После создания индекса:
1. Иванов
2. Иванов
3. Иванов
4. Петров
5. Петров
6. Петров
  
Наверх
 
IP записан
 
kms
1c++ power user
1c++ moderator
Отсутствует


я хочу, чтоб сюда проложили
дорогу оттуда...

Сообщений: 4632
Зарегистрирован: 19. Мая 2006
Re: ИТЗ: порядок и индексирование
Ответ #6 - 13. Декабря 2007 :: 11:21
Печать  
Подожди-ка.

Ты имеешь в виду
1. что здесь тоже итерирование упорядочено без учета номеров строк? - так это понятно, дерево есть дерево, оно по-другому не может.
2. что неуникальный индекс не обладает свойством стабильности?

П.2 действительно наиболее интересный.

Поскольку никто не гарантирует, что индекс ИТ обладает свойством стабильности (сохранение исходного порядка строк для равных значений при сортировке), мой алгоритм в №3 действительно неверен.

Т.е. нужно на самом деле 2 индекса: уникальный по "Имя", и еще один по "Имя, НомерСтроки".

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

Далее - все как и в №3.

P.S.
На самом деле, индекс, возможно, сортирует стабильно; я помню, что даже Леша Диркс использует это свойство в тестах ИТ.
Но если по правде, либо это свойство должно быть гарантировано документацией, либо его использовать нельзя.

P.P.S.
Может, и не очень простой алгоритм - ну что тут делать, надо значит надо Улыбка
  

De quelle planète es-tu?
Наверх
 
IP записан
 
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: ИТЗ: порядок и индексирование
Ответ #7 - 13. Декабря 2007 :: 11:27
Печать  
Выход, конечно, есть. Приминительно к моей задаче, я сделаю так:
Код
Выбрать все
тз=СоздатьОбъект("ТаблицаЗначений");
	ИТЗ.Выгрузить(тз);
	тз.Свернуть(стрИмя,"");
	//если надо в список, то делаем ещё: тз.Выгрузить(спУникальныхИменСПервоначальнойСортировкой,,,стрИмя); 

  
Наверх
 
IP записан
 
kms
1c++ power user
1c++ moderator
Отсутствует


я хочу, чтоб сюда проложили
дорогу оттуда...

Сообщений: 4632
Зарегистрирован: 19. Мая 2006
Re: ИТЗ: порядок и индексирование
Ответ #8 - 13. Декабря 2007 :: 11:39
Печать  
Гениально.
С тем же успехом ты мог бы использовать ИТЗ.Свернуть(). Подмигивание

Я просто тебе пытался описать алгоритм, который обеспечивает теоретические гарантии стабильности.
А ИТЗ.Свернуть(), ТЗ.Свернуть(), любые индексы ИТЗ пока ничего такого не гарантируют.

ОК, решение найдено.

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

De quelle planète es-tu?
Наверх
 
IP записан
 
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: ИТЗ: порядок и индексирование
Ответ #9 - 13. Декабря 2007 :: 11:45
Печать  
kms писал(а) 13. Декабря 2007 :: 11:39:
Гениально.
С тем же успехом ты мог бы использовать ИТЗ.Свернуть(). Подмигивание

Я просто тебе пытался описать алгоритм, который обеспечивает теоретические гарантии стабильности.
А ИТЗ.Свернуть(), ТЗ.Свернуть(), любые индексы ИТЗ пока ничего такого не гарантируют.

Я понял твою идею и изначально хотел примерно тоже самое и лепить, но думается мне, что все эти постройки начинают возводиться на фундаменте, который не проверен. Да и сами постройки, мягко сказать, не прозрачны.
П.С. А текущую ИТЗ мне сворачивать нельзя, она мне ещё понадобится!
П.С.С. можно ещё и сгруппировать  Язык
  
Наверх
 
IP записан
 
kms
1c++ power user
1c++ moderator
Отсутствует


я хочу, чтоб сюда проложили
дорогу оттуда...

Сообщений: 4632
Зарегистрирован: 19. Мая 2006
Re: ИТЗ: порядок и индексирование
Ответ #10 - 13. Декабря 2007 :: 11:59
Печать  
JohnyDeath писал(а) 13. Декабря 2007 :: 11:45:
Я понял твою идею и изначально хотел примерно тоже самое и лепить, но думается мне, что все эти постройки начинают возводиться на фундаменте, который не проверен.

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

Цитата:
Да и сами постройки, мягко сказать, не прозрачны.

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

De quelle planète es-tu?
Наверх
 
IP записан
 
ADirks
1c++ developer
1c++ moderator
Отсутствует


А нужны ли мы нам?

Сообщений: 692
Местоположение: Новосибирск
Зарегистрирован: 22. Мая 2006
Пол: Мужской
Re: ИТЗ: порядок и индексирование
Ответ #11 - 13. Декабря 2007 :: 13:09
Печать  
2 kms,  насчёт стабильности:  при добавлении строк в индекс таблица тупо перебирается от начала, безо всяких хитростей, т.о. порядок строк в самом индексе 99.999% останется неизменным. В итераторах тоже везде обход идёт по порядку, так что с той же вероятностью можно утверждать, что порядок сохраняется.
Но 100% гарантии нет, потому что специально я к этому не стремился - так проще реализация, вот и всё. 

Для уникальных индексов всегда берётся первая попавшаяся строка - здесь гарантия 100%.
Для уникальных итераторов по неуникальным индексам тоже всегда берётся первая попавшаяся строка, как если бы индекс был уникальным.
  
Наверх
 
IP записан
 
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: ИТЗ: порядок и индексирование
Ответ #12 - 13. Декабря 2007 :: 14:04
Печать  
ADirks писал(а) 13. Декабря 2007 :: 13:09:
Для уникальных индексов всегда берётся первая попавшаяся строка - здесь гарантия 100%.
Для уникальных итераторов по неуникальным индексам тоже всегда берётся первая попавшаяся строка, как если бы индекс был уникальным.

А что значит "первая попавшаяся строка"? Я понимаю эту фразу как первая из основного индекса. Если так, то почему "неправильно" отрабатывает пример из поста 0?
  
Наверх
 
IP записан
 
kms
1c++ power user
1c++ moderator
Отсутствует


я хочу, чтоб сюда проложили
дорогу оттуда...

Сообщений: 4632
Зарегистрирован: 19. Мая 2006
Re: ИТЗ: порядок и индексирование
Ответ #13 - 13. Декабря 2007 :: 14:05
Печать  
ADirks

Да, похоже, разобрались:

ADirks писал(а) 13. Декабря 2007 :: 13:09:
насчёт стабильности:  при добавлении строк в индекс таблица тупо перебирается от начала, безо всяких хитростей, т.о. порядок строк в самом индексе 99.999% останется неизменным. В итераторах тоже везде обход идёт по порядку, так что с той же вероятностью можно утверждать, что порядок сохраняется.

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

Цитата:
Но 100% гарантии нет, потому что специально я к этому не стремился - так проще реализация, вот и всё.  

Совершенно верно.
Более того, в процессе работы с индексом свойство стабильности теряется.
И это правильно, ибо поддержание стабильности индекса потребовало бы дополнительных затрат.
Это не нужно; достаточно того, что мы можем получить стабильный отсортированный массив непосредственно после создания индекса.

Вот иллюстрация потери упорядоченности номеров строк в пределах равного ключа:
Код
Выбрать все
Процедура Добавить(__т, __знач)
	__т.НоваяСтрока();
	__т.Значение =__знач;
	__т.НомерСтр =__т.НомерСтроки;
КонецПроцедуры

Процедура Сформировать()
	_т =СоздатьОбъект("ИндексированнаяТаблица");
	_т.НоваяКолонка("Значение");
	_т.НоваяКолонка("НомерСтр");

	Добавить(_т, 5);
	Добавить(_т, 3);
	Добавить(_т, 5);
	Добавить(_т, 3);

	_т.ДобавитьИндекс("Значение", "Значение");
	_т.Показать("Значение"); // результат стабилен

	_т.Установить(2, "Значение", 5);
	_т.Показать("Значение"); // результат "нестабилен"

	_т.Установить(2, "Значение", 3);
	_т.Показать("Значение"); // результат "нестабилен"

	_т.Свернуть(, "", "Значение");
	_т.Показать("Значение"); // результат "нестабилен"
КонецПроцедуры
 



Цитата:
Для уникальных индексов всегда берётся первая попавшаяся строка - здесь гарантия 100%.

Принято; так и запишем.

Цитата:
Для уникальных итераторов по неуникальным индексам тоже всегда берётся первая попавшаяся строка, как если бы индекс был уникальным.

Здесь, я думаю, не совсем так.
Непосредственно после построения индекса уникальное итерирование по неуникальному индексу даст строки с минимальными номерами для каждого ключа.
Или я где-то ошибаюсь? Подмигивание

Резюме:
1. Уникальные индексы никаких гарантий относительно расположения строки не дают.
2. Неуникальные индексы дают 100% гарантию стабильности непосредственно после построения индекса.
3. Гарантии аннулируются при любом дальнейшем изменении индекса (можно расслабить ограничение, но не вижу смысла).

Неплохо.
А я, каюсь, поначалу думал, что из такой непонятной темы ничего хорошего не получится. Улыбка
  

De quelle planète es-tu?
Наверх
 
IP записан
 
kms
1c++ power user
1c++ moderator
Отсутствует


я хочу, чтоб сюда проложили
дорогу оттуда...

Сообщений: 4632
Зарегистрирован: 19. Мая 2006
Re: ИТЗ: порядок и индексирование
Ответ #14 - 13. Декабря 2007 :: 14:14
Печать  
JohnyDeath писал(а) 13. Декабря 2007 :: 14:04:
А что значит "первая попавшаяся строка"? Я понимаю эту фразу как первая из основного индекса. Если так, то почему "неправильно" отрабатывает пример из поста 0?

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

Кстати, с учетом изложенных выше гарантий, использовать алгоритм из ответов №3, №4 можно 100% безопасно.
Конечно, если после индексации сам индекс не претерпевает никаких изменений.

Собственно, свертка в ИТЗ именно так (и с теми же гарантиями) и работает.
  

De quelle planète es-tu?
Наверх
 
IP записан
 
Переключение на Главную Страницу Страницы: [1] 2 
ОтправитьПечать