Вопрос по поиску элемента из упорядоченного по возрастанию массива
Если про элементы, кроме того, что их сравнивать можно, ничего не известно, то никто не знает.
Кто-то знает более быстрый способ?Бог.
Элементы в массиве упорядочены по возрастанию.
2 олл:
Напишите "нет", если не знаете более быстродействующего алгоритма.
2 олл:
Напишите "нет", если не знаете более быстродействующего алгоритма.
если ты про распределение элементов ничего не знаешь то асимптотику ты не улучшишь.
за константу на конкретном железе можно ещё побороться.
возможно стоит проиграться с кэш-линиями и сравнивать больше чем один рядом стоящий элемент, всё равно они уже в кёш загружены, этим можно константу уменьшить немного,
да и на последних шагах простое сканирование уже лучше будет работать чем дихотомия.
за константу на конкретном железе можно ещё побороться.
возможно стоит проиграться с кэш-линиями и сравнивать больше чем один рядом стоящий элемент, всё равно они уже в кёш загружены, этим можно константу уменьшить немного,
да и на последних шагах простое сканирование уже лучше будет работать чем дихотомия.
Я знаю способ O(1).
---
...Я работаю антинаучным аферистом...
---
...Я работаю антинаучным аферистом...
Я знаю способ O(1).Ткнуть пальцем в элемент
?Если мыслить образно --- да.
---
...Я работаю антинаучным аферистом...
---
...Я работаю антинаучным аферистом...
> если ты про распределение элементов ничего не знаешь
> то асимптотику ты не улучшишь
Это неправда, есть способ O(1 не зависящий от распределения.
---
"Расширь своё сознание!"
> то асимптотику ты не улучшишь
Это неправда, есть способ O(1 не зависящий от распределения.
---
"Расширь своё сознание!"
работающий с вероятностью >= 1/n ? =)
Да.
Вероятность единица.
---
"Расширь своё сознание!"
Вероятность единица.
---
"Расширь своё сознание!"
Хотя можно и сократить, чтобы уменьшить константу.
---
...Я работаю антинаучным аферистом...
---
...Я работаю антинаучным аферистом...
n == 1 ?
n любое разумное.
---
"Расширь своё сознание!"
---
"Расширь своё сознание!"
n любое разумное"разумное" не интересно: ln(n) <= 64 = O(1)
Да пусть хоть 1024.
Константу можно сделать очень даже небольшой.
---
...Я работаю антинаучным аферистом...
Константу можно сделать очень даже небольшой.
---
...Я работаю антинаучным аферистом...
Мы все в нетерпении! Открой нам глаза на сей чудесный алгоритм, описания которого нет во всём интернете!
сколько ресурсов нужно алгоритму?
массив из n элементов, элементы приадлежат множеству мощности M
массив из n элементов, элементы приадлежат множеству мощности M
М естественно =)
Только, как справедливо заметил мне Мадкроз в приватной беседе, перед поиском нужно ещё потратить O(max(m, n на подготовку данных.
угу, есть такое.
> сколько ресурсов нужно алгоритму?
Да нисколько.
---
...Я работаю антинаучным аферистом...
P.S. Просто нужно иное представление массива.
Да нисколько.
---
...Я работаю антинаучным аферистом...
P.S. Просто нужно иное представление массива.
угу, так что, как опять же заметил мне Мадкроз в приватной беседе, алгоритм Контры не решает задачу.
всмысле?
Ну как, задача - есть массив, нужно узнать, есть ли в нём данный элемент. Контра говорит: "мне нужно О(1)". Он нагло песдит, потому что ему нужно как минимум О(n) для подготовки "другого представления массива", причём ещё по-моему он нагло песдит второй раз, когда говорит, что его алгоритму не нужно дополнительных ресурсов, т.к. его "другое представление" явно занимает больше памяти, чем исходное.
Хотя мб он не считает планку ассоциативной памяти дополнительным ресурсом, не знаю. Он может.
Хотя мб он не считает планку ассоциативной памяти дополнительным ресурсом, не знаю. Он может.
т.е. даже не предполагается, что массив уже подготовлен нужным образом?
в исходном посте это не специфицировано.
в исходном посте это не специфицировано.
"Допустим, есть упорядоченный по возрастанию (можно и по убыванию, но здесь по возрастанию) массив."
По-моему всё специфицировано как нельзя более чётко.
По-моему всё специфицировано как нельзя более чётко.
что, представление контры не есть "упорядоченный по возрастанию массив список"?
> нужно как минимум О(n) для подготовки "другого представления массива",
Не нужно. В условии сказано, что массив уже есть.
В оценку не входит время заполнения массива,
иначе даже логарифмическое время недостижимо.
---
...Я работаю антинаучным аферистом...
Не нужно. В условии сказано, что массив уже есть.
В оценку не входит время заполнения массива,
иначе даже логарифмическое время недостижимо.
---
...Я работаю антинаучным аферистом...
Я полагаю, что нет.
Я полагаю, что представление контры есть массив бит или что-то в этом роде.
Это совершенно разные вещи, я полагаю.
Я полагаю, что представление контры есть массив бит или что-то в этом роде.
Это совершенно разные вещи, я полагаю.
уж не придираешься ли ты к формулировке?
она кривовата конечно. речь конечно о поиске позиции элемента.
она кривовата конечно. речь конечно о поиске позиции элемента.
Нет. Я говорю именно о позиции аргумента,
либо выделенное значение в случае отсутствия.
---
...Я работаю антинаучным аферистом...
либо выделенное значение в случае отсутствия.
---
...Я работаю антинаучным аферистом...
А твоё представление не есть массив бит?
Какое?
---
...Я работаю антинаучным аферистом...
Какое?
---
...Я работаю антинаучным аферистом...
Моё (и автора) представление есть массив элементов, отсортированных по возрастанию. Подразумевается наличие операции сравнения двух элементов.
это ведь всё равно массив бит, не правда ли?
и автор ведь не специфицировал вид массива?
и автор ведь не специфицировал вид массива?
Моё представление тоже массив элементов, отсортированных по возрастанию.
Наличие операции сравнения не обязательно,
порядок в заполненном массиве определяет всё.
---
...Я работаю антинаучным аферистом...
Наличие операции сравнения не обязательно,
порядок в заполненном массиве определяет всё.
---
...Я работаю антинаучным аферистом...
А ты когда-нибудь расскажешь свой способ, или можно дальше не читать тред?
Ну давай, рассказывай, самому уже не терпится. Неужели такой есть?
Кроме того, массив состоит из нескольких тысяч элементов, в противном случае логарифмическая ассимптотика особого смысла не имела бы.
Кроме того, массив состоит из нескольких тысяч элементов, в противном случае логарифмическая ассимптотика особого смысла не имела бы.
как правильно сказал КОНТРА, нужно просто другое представление массива.
Кстати, мы что ИЗМЕРЯЕМ в этом алгоритме?
Кстати, мы что ИЗМЕРЯЕМ в этом алгоритме?
Основная мысль: закодировать массив так, чтобы определение
положения элемента свелось к выборке из памяти.
Можно --- к каскаду выборок.
---
"Расширь своё сознание!"
положения элемента свелось к выборке из памяти.
Можно --- к каскаду выборок.
---
"Расширь своё сознание!"
как правильно сказал КОНТРА, нужно просто другое представление массива.Да ничего не измеряем, просто ищем позицию данного элемента, который равен, например, 7.
Кстати, мы что ИЗМЕРЯЕМ в этом алгоритме?
А какое представление массива должно быть?
Если нужен какой-то оптимальный алгоритм, то нужно как-то уметь сравнивать алгоритмы. т.е. ввести что-то типа "порядка", "упорядочить" алогоритмы. Или сопоставить каждому алгоритму (или некоторому выполнению алгоритма)некое действительное число. И по этому числу судить что какой-то алгоритм лучше а какой-то хуже. Если измерять нечего то о каком выборе между какими-то двумя может идти речь, если они одинаковы? (одинаково неизмеримы).
И хотелось бы, чтобы этот параметр не зависел от архитектуры, времени года и т.п.
В качестве этого параметра нельзя брать "время" в физическом смысле. Потому что может запросто оказаться, что на одном процессоре одни алгоритмы работают быстрее ("лучше" а другие - медленнее("хуже" а втором процессоре - всё наоборот.
"Количество операций" - тоже довольно-таки туманный термин.
"Взять значение элемента с номером N" - сколько операций?
"сравнить элемента с номерами N с другим элементом (без номера)" - сколько операций? и т.п.
нужно будет наложить вес на все шаги алгоритма (что не было сделано, между прочим) и в случае, например, если операция сравнения двух элементов будет очень лёгкой, а выборка значения элемента очень тяжёлой, то оптимальный алгоритм может быть устроен совсем по-другому.
По поводу устройства массива. Поскольку в первом посте не указан не только язык и архитектура но и способ организации массива, то авторы алгоритмов вправе предполагать любое представление массива, им удобное.
Например. В OpenGL различные поверхности сложной структуры можно задавать элементами - треугольниками. Соответственно, поверхость = массив треугольников.
Так вот, для оптимизации в том числе и поиска и сортировки, есть договорённость, что массив представляется не отдельными треугольниками, а полосками (stripe) - последовательности смежных треугольников объединяются и передаются сразу каскадом.
И хотелось бы, чтобы этот параметр не зависел от архитектуры, времени года и т.п.
В качестве этого параметра нельзя брать "время" в физическом смысле. Потому что может запросто оказаться, что на одном процессоре одни алгоритмы работают быстрее ("лучше" а другие - медленнее("хуже" а втором процессоре - всё наоборот.
"Количество операций" - тоже довольно-таки туманный термин.
"Взять значение элемента с номером N" - сколько операций?
"сравнить элемента с номерами N с другим элементом (без номера)" - сколько операций? и т.п.
нужно будет наложить вес на все шаги алгоритма (что не было сделано, между прочим) и в случае, например, если операция сравнения двух элементов будет очень лёгкой, а выборка значения элемента очень тяжёлой, то оптимальный алгоритм может быть устроен совсем по-другому.
По поводу устройства массива. Поскольку в первом посте не указан не только язык и архитектура но и способ организации массива, то авторы алгоритмов вправе предполагать любое представление массива, им удобное.
Например. В OpenGL различные поверхности сложной структуры можно задавать элементами - треугольниками. Соответственно, поверхость = массив треугольников.
Так вот, для оптимизации в том числе и поиска и сортировки, есть договорённость, что массив представляется не отдельными треугольниками, а полосками (stripe) - последовательности смежных треугольников объединяются и передаются сразу каскадом.
> Основная мысль: закодировать массив так, чтобы определение
положения элемента свелось к выборке из памяти.
это возможно только для регулярного набора элементов, для произвольного упорядоченного набора - такого способа кодирования не существует.
положения элемента свелось к выборке из памяти.
это возможно только для регулярного набора элементов, для произвольного упорядоченного набора - такого способа кодирования не существует.
Это возможно для любого набора.
Способ кодирования очевиден.
---
...Я работаю антинаучным аферистом...
P.S. Что? ООП не спасает? Задачка-то плёвая, мог бы свой хвалёный
полиморфизм пристегнуть.
Способ кодирования очевиден.
---
...Я работаю антинаучным аферистом...
P.S. Что? ООП не спасает? Задачка-то плёвая, мог бы свой хвалёный
полиморфизм пристегнуть.
Способ кодирования очевиден.
---
вихри враждебные веют над нами
> Способ кодирования очевиден.
т.е. ты его сейчас нам представишь в виде одного предложения.
и этот способ мы сможем без всяких оговорок применить к любой реальной задачи на рельных ограничениях (отсутствие бесконечной памяти, отсутствие бесконечного времени, отсутствие мгновенного доступа и т.д.)
т.е. ты его сейчас нам представишь в виде одного предложения.
и этот способ мы сможем без всяких оговорок применить к любой реальной задачи на рельных ограничениях (отсутствие бесконечной памяти, отсутствие бесконечного времени, отсутствие мгновенного доступа и т.д.)
> т.е. ты его сейчас нам представишь в виде одного предложения.
Уже представил: определение позиции сводится к выборке из памяти.
Для насильников (если им это всё ещё непонятно это выглядит так:
где ord даёт представление в виде целого числа, elem ---
элемент массива, base --- указатель на ту область памяти,
которая хранит положения элементов в виде целых чисел
от 0 ("отсутствует") до размера массива ("последний").
> и этот способ мы сможем без всяких оговорок применить
> к любой реальной задачи на рельных ограничениях
Да.
---
...Я работаю антинаучным аферистом...
Уже представил: определение позиции сводится к выборке из памяти.
Для насильников (если им это всё ещё непонятно это выглядит так:
posn = base[ord(elem)];
где ord даёт представление в виде целого числа, elem ---
элемент массива, base --- указатель на ту область памяти,
которая хранит положения элементов в виде целых чисел
от 0 ("отсутствует") до размера массива ("последний").
> и этот способ мы сможем без всяких оговорок применить
> к любой реальной задачи на рельных ограничениях
Да.
---
...Я работаю антинаучным аферистом...
> Способ кодирования очевиден
> где ord даёт представление в виде целого числа
вообще-то ord это и есть функция кодирования.
и именно ее алгоритм ты и хотел описать в виде одного предложения.
код который ты привел это уже выборка на основе кодирования.
> где ord даёт представление в виде целого числа
вообще-то ord это и есть функция кодирования.
и именно ее алгоритм ты и хотел описать в виде одного предложения.
код который ты привел это уже выборка на основе кодирования.
> вообще-то ord это и есть функция кодирования.
Это функция кодирования элементов, она известна независимо
от способа кодирования массива.
---
...Я работаю антинаучным аферистом...
Это функция кодирования элементов, она известна независимо
от способа кодирования массива.
---
...Я работаю антинаучным аферистом...
Имеется массив вещественных чисел и еще одно вещественное число, которое надо найти в массиве (сравнивать предполагается с точностью, которую позволяет достичь тип double). ord не подойдет.
У тебя есть веские основания или ты просто подумал, что раз
это число с плав. запятой, у него нет однозначного представления?
---
...Я работаю антинаучным аферистом...
это число с плав. запятой, у него нет однозначного представления?
---
...Я работаю антинаучным аферистом...
Я не понял. Что делать, если функция ord(elem) не может быть задана? Или мы здесь рассматриваем чисто теоретическую задачу, где целое число может принимать сколь угодно большие значения, и при этом мы умеем адресовать base[ord(elem)] за O(1)?posn = base[ord(elem)];где ord даёт представление в виде целого числа
в силу того, что компьютеры конечны, целое число в данном контексте не может принимать сколь угодно большое значение. граница есть. но она далеко не 2^32 или 2^64, как может показаться некоторым.
для начала хотя бы для строк ord придумайте, что бы он не хотел массив бесконечной длины.
> Что делать, если функция ord(elem) не может быть задана?
Этого не бывает.
То есть, такое бывает только тогда, когда ты вообще не умеешь
выделять объекты, а раз так, тебе ничто не поможет.
---
Q18: А что такое "БК-0010"?
A18: Да в кривых руках и DeepBlue калькулятором будет.
Этого не бывает.
То есть, такое бывает только тогда, когда ты вообще не умеешь
выделять объекты, а раз так, тебе ничто не поможет.
---
Q18: А что такое "БК-0010"?
A18: Да в кривых руках и DeepBlue калькулятором будет.
> граница есть. но она далеко не 2^32 или 2^64, как может показаться некоторым.
только выборка сразу станет скорее O(ln n чем O(1)
только выборка сразу станет скорее O(ln n чем O(1)
> Научить пользоваться FSF Directory?
на все эти хэши можно придумать пример, когда на конкретном примере будет O(n).
Ты обещал, что будет работать везде, всегда и бесплатно.
на все эти хэши можно придумать пример, когда на конкретном примере будет O(n).
Ты обещал, что будет работать везде, всегда и бесплатно.
> на все эти хэши можно придумать пример, когда на конкретном примере будет O(n).
На указанные --- нельзя, это их свойство такое.
> Ты обещал, что будет работать везде, всегда и бесплатно.
Я ничего не обещал.
Тем более --- бесплатно.
---
"Аллах не ведёт людей неверных."
На указанные --- нельзя, это их свойство такое.
> Ты обещал, что будет работать везде, всегда и бесплатно.
Я ничего не обещал.
Тем более --- бесплатно.
---
"Аллах не ведёт людей неверных."
> На указанные --- нельзя, это их свойство такое.
у него более узкое свойство, чем тебе бы хотелось.
например, приведенный тобой gperf не работает с заранее не известным набором строк.
у него более узкое свойство, чем тебе бы хотелось.
например, приведенный тобой gperf не работает с заранее не известным набором строк.
>> На указанные --- нельзя, это их свойство такое.
> у него более узкое свойство, чем тебе бы хотелось.
У него как раз то свойство, которое и хотелось.
> например, приведенный тобой gperf не работает с заранее не известным набором строк.
У тебя отсортированный массив состоит из неизвестного набора строк?
---
"Аллах не ведёт людей неверных."
> у него более узкое свойство, чем тебе бы хотелось.
У него как раз то свойство, которое и хотелось.
> например, приведенный тобой gperf не работает с заранее не известным набором строк.
У тебя отсортированный массив состоит из неизвестного набора строк?
---
"Аллах не ведёт людей неверных."
> У тебя отсортированный массив состоит из неизвестного набора строк?
зато набор искомых строк - скорее неизвестен, чем известен.
зато набор искомых строк - скорее неизвестен, чем известен.
У тебя есть веские основания или ты просто подумал, что разда нет, мне интересно, где ты собираешься хранить массив с индексом такого размера, в который можно вместить все числа с плавающей точкой, которые можно различить.
это число с плав. запятой, у него нет однозначного представления?
Научить пользоваться механизмом исключений?
---
"Аллах не ведёт людей неверных."
---
"Аллах не ведёт людей неверных."
В памяти.
---
"Аллах не ведёт людей неверных."
---
"Аллах не ведёт людей неверных."
> Научить пользоваться механизмом исключений?
во-первых, исключения здесь уж точно не причем
во-вторых, я был не прав, когда говорил, что нам чем-то мешает неизвестность искомых строк.
в-третьих, чему равна сложность построения этих самых хэшей? на сайте у них ничего полезного по этому поводу не написано.
во-первых, исключения здесь уж точно не причем
во-вторых, я был не прав, когда говорил, что нам чем-то мешает неизвестность искомых строк.
в-третьих, чему равна сложность построения этих самых хэшей? на сайте у них ничего полезного по этому поводу не написано.
> чему равна сложность построения этих самых хэшей?
К поиску это не относится.
---
"Аллах не ведёт людей неверных."
К поиску это не относится.
---
"Аллах не ведёт людей неверных."
хаха!
Fj с Мадкрозом, давно угадавшие читерский алгоритм Контры уже давно забили на этот говнотред
Fj с Мадкрозом, давно угадавшие читерский алгоритм Контры уже давно забили на этот говнотред
зная кохпту, можно легко догадаться что алгоритм читерский, а какой конкретно не так и важно.
Я решаю _поставленную_ задачу, а не некоторую пиленую,
получаемую введением дополнительных ограничений.
---
"Аллах не ведёт людей неверных."
получаемую введением дополнительных ограничений.
---
"Аллах не ведёт людей неверных."
Ты занимаешься антинаучным аферизмом.
Поставлена задача: дан массив элементов, отсортированных в порядке возрастания. Это могут быть хендлы (int64) на какие-то объекты операционной системы плюс апи функция сравнения двух объектов по хендлу. Нука расскажика как ты будешь получать "другое представление массива" в таком случае?
Не говоря уж о том, что даже если стоит просто задача найти данный элемент в массиве обычных инт32, тебе понадобится 16 гигов памяти под твой "преобразованный" массив, если я правильно понимаю, какой алгоритм ты имеешь в виду.
Поставлена задача: дан массив элементов, отсортированных в порядке возрастания. Это могут быть хендлы (int64) на какие-то объекты операционной системы плюс апи функция сравнения двух объектов по хендлу. Нука расскажика как ты будешь получать "другое представление массива" в таком случае?
Не говоря уж о том, что даже если стоит просто задача найти данный элемент в массиве обычных инт32, тебе понадобится 16 гигов памяти под твой "преобразованный" массив, если я правильно понимаю, какой алгоритм ты имеешь в виду.
Либо у тебя получится, цитирую, каскад сравнений, который даёт ту же логарифмическую сложность.
Либо ты как-то проходишь по массиву (за О(n)!) и хитроумно хешируешь элементы, получая О(1) в лучшем случае и тот же логарифм в худшем.
Либо ты как-то проходишь по массиву (за О(n)!) и хитроумно хешируешь элементы, получая О(1) в лучшем случае и тот же логарифм в худшем.
> Поставлена задача: дан массив элементов, отсортированных в порядке возрастания.
Ну и у меня то же: дан массив элементов, отсортированных в порядке возрастания.
Сущность элементов, хендлы это или нет, не нужна.
> Нука расскажика как ты будешь получать "другое представление массива" в таком случае?
Точно так же, как и ты: либо сортировкой исходного,
либо последовательным заполнением.
> Не говоря уж о том, что даже если стоит просто задача найти
> данный элемент в массиве обычных инт32, тебе понадобится
> 16 гигов памяти под твой "преобразованный" массив,
> если я правильно понимаю, какой алгоритм ты имеешь в виду.
Ограничений на объём памяти в условии задачи нет.
Способ с использованием совершенных хешей требует меньше памяти.
---
"Аллах не ведёт людей неверных."
Ну и у меня то же: дан массив элементов, отсортированных в порядке возрастания.
Сущность элементов, хендлы это или нет, не нужна.
> Нука расскажика как ты будешь получать "другое представление массива" в таком случае?
Точно так же, как и ты: либо сортировкой исходного,
либо последовательным заполнением.
> Не говоря уж о том, что даже если стоит просто задача найти
> данный элемент в массиве обычных инт32, тебе понадобится
> 16 гигов памяти под твой "преобразованный" массив,
> если я правильно понимаю, какой алгоритм ты имеешь в виду.
Ограничений на объём памяти в условии задачи нет.
Способ с использованием совершенных хешей требует меньше памяти.
---
"Аллах не ведёт людей неверных."
> Либо у тебя получится, цитирую, каскад сравнений,
> который даёт ту же логарифмическую сложность.
Нет, длина цепочки жёстко задана при реализации,
поэтому от объёма не зависит.
> Либо ты как-то проходишь по массиву (за О(n)!) и хитроумно хешируешь элементы,
Даже если так, это не входит во время поиска, поэтому O(1) в любом случае.
---
"Аллах не ведёт людей неверных."
> который даёт ту же логарифмическую сложность.
Нет, длина цепочки жёстко задана при реализации,
поэтому от объёма не зависит.
> Либо ты как-то проходишь по массиву (за О(n)!) и хитроумно хешируешь элементы,
Даже если так, это не входит во время поиска, поэтому O(1) в любом случае.
---
"Аллах не ведёт людей неверных."
> Точно так же, как и ты: либо сортировкой исходного
Исходный отсортирован. Точка.
> Ограничений на объём памяти в условии задачи нет.
Ты забываешь, что обнуление 16 гигов памяти занимает довольно-таки дофига времени. Существенно больше, чем то, что нормальные люди подразумевают под О(1).
> Способ с использованием совершенных хешей требует меньше памяти.
Исчо раз.
Как ты будешь получать свои совершенные хеши для объектов, о которых ты знаешь только хендл? Учитывай, что в managed environment значение тайпкаста хендла в соответствующий инт может меняться со временем.
Исходный отсортирован. Точка.
> Ограничений на объём памяти в условии задачи нет.
Ты забываешь, что обнуление 16 гигов памяти занимает довольно-таки дофига времени. Существенно больше, чем то, что нормальные люди подразумевают под О(1).
> Способ с использованием совершенных хешей требует меньше памяти.
Исчо раз.
Как ты будешь получать свои совершенные хеши для объектов, о которых ты знаешь только хендл? Учитывай, что в managed environment значение тайпкаста хендла в соответствующий инт может меняться со временем.
Даже если так, это не входит во время поискаДаааа? Как интересно... Тебе ясно и недвусмысленно сказали: дан массив бла бла бла. Ты говоришь - а дайте-ка мне ещё один массив с размерностью 2^^(количество бит в хеше заполните его, собственно, хешами, и тогда я вам сделаю поиск элемента за О(1) в лучшем случае и О(n) в худшем.
Если это решение задачи, то я прям даже не могу представить не-решение.
>> Точно так же, как и ты: либо сортировкой исходного
> Исходный отсортирован. Точка.
У меня тоже отсортирован.
>> Ограничений на объём памяти в условии задачи нет.
> Ты забываешь, что обнуление 16 гигов памяти занимает
> довольно-таки дофига времени.
Ты сам это время к поиску не относишь: заполнение массива
занимает O(n) времени, так что O(log n) ты ни в жисть не получишь.
>> Способ с использованием совершенных хешей требует меньше памяти.
> Как ты будешь получать свои совершенные хеши для
> объектов, о которых ты знаешь только хендл?
Это не имеет значения, поскольку это делается не во время поиска.
---
"Аллах не ведёт людей неверных."
> Исходный отсортирован. Точка.
У меня тоже отсортирован.
>> Ограничений на объём памяти в условии задачи нет.
> Ты забываешь, что обнуление 16 гигов памяти занимает
> довольно-таки дофига времени.
Ты сам это время к поиску не относишь: заполнение массива
занимает O(n) времени, так что O(log n) ты ни в жисть не получишь.
>> Способ с использованием совершенных хешей требует меньше памяти.
> Как ты будешь получать свои совершенные хеши для
> объектов, о которых ты знаешь только хендл?
Это не имеет значения, поскольку это делается не во время поиска.
---
"Аллах не ведёт людей неверных."
Да!
"Дан массив" означает, что массив уже построен.
В каком виде он построен в задаче --- не оговорено.
---
"Аллах не ведёт людей неверных."
"Дан массив" означает, что массив уже построен.
В каком виде он построен в задаче --- не оговорено.
---
"Аллах не ведёт людей неверных."
> Это не имеет значения, поскольку это делается не во время поиска.
Это имеет значение, поскольку ты физически не можешь построить хеш (например) для объекта, на который у тебя есть только хендл, причём значение хендла (полученное в результате тайпкаста на инт соответствующей размерности) может менятся после каждой сборки мусора.
Ну не можешь, ну извини.
> Ты сам это время к поиску не относишь: заполнение массива
> занимает O(n) времени, так что O(log n) ты ни в жисть не получишь.
Массив дан изначально, как он получен - неважно. К компу подсоединено внешнее устройство, которое по РС232 рассказывает размер массива и результат сравнения двух элементов.
> В каком виде он построен в задаче --- не оговорено.
Хуясе. Скажика, как ты умудряешься привести фразу "Допустим, есть упорядоченный по возрастанию (можно и по убыванию, но здесь по возрастанию) массив" к наличию второго, дополнительного массива, в котором лежат индексы элементов с соответствующим хешем? Я настаиваю на наличии второго массива, ибо только из него хй ты получишь оригинальные значения.
Это имеет значение, поскольку ты физически не можешь построить хеш (например) для объекта, на который у тебя есть только хендл, причём значение хендла (полученное в результате тайпкаста на инт соответствующей размерности) может менятся после каждой сборки мусора.
Ну не можешь, ну извини.
> Ты сам это время к поиску не относишь: заполнение массива
> занимает O(n) времени, так что O(log n) ты ни в жисть не получишь.
Массив дан изначально, как он получен - неважно. К компу подсоединено внешнее устройство, которое по РС232 рассказывает размер массива и результат сравнения двух элементов.
> В каком виде он построен в задаче --- не оговорено.
Хуясе. Скажика, как ты умудряешься привести фразу "Допустим, есть упорядоченный по возрастанию (можно и по убыванию, но здесь по возрастанию) массив" к наличию второго, дополнительного массива, в котором лежат индексы элементов с соответствующим хешем? Я настаиваю на наличии второго массива, ибо только из него хй ты получишь оригинальные значения.
>> Это не имеет значения, поскольку это делается не во время поиска.
> Это имеет значение, поскольку ты физически не можешь
> построить хеш (например) для объекта, на который у тебя
> есть только хендл, причём значение хендла (полученное в
> результате тайпкаста на инт соответствующей размерности)
> может менятся после каждой сборки мусора.
И что препятствует?
То, что ты записывал в массив, не меняется произвольно,
соответственно, записываемый хендл и хешируется.
Если сборщик мусора захочет его обновить прямо в массиве,
это его личные трудности, никто не мешает сделать это правильно.
>> Ты сам это время к поиску не относишь: заполнение массива
>> занимает O(n) времени, так что O(log n) ты ни в жисть не получишь.
> Массив дан изначально, как он получен - неважно.
> К компу подсоединено внешнее устройство, которое по РС232
> рассказывает размер массива и результат сравнения двух элементов.
И?
Время передачи массива через этот канал ты сам же не учитываешь,
потому что это время --- опять не меньше O(n).
>> В каком виде он построен в задаче --- не оговорено.
> Скажика,
"Скажи-ка."
> как ты умудряешься привести фразу "Допустим, есть упорядоченный
> по возрастанию (можно и по убыванию, но здесь по возрастанию)
> массив" к наличию второго, дополнительного массива, в котором
> лежат индексы элементов с соответствующим хешем?
Ты когда-нибудь задумывался, что делается внутри обвязки к памяти?
Может, у тебя доступ к элементу массива не O(1 а ты это не учитываешь.
---
"Аллах не ведёт людей неверных."
> Это имеет значение, поскольку ты физически не можешь
> построить хеш (например) для объекта, на который у тебя
> есть только хендл, причём значение хендла (полученное в
> результате тайпкаста на инт соответствующей размерности)
> может менятся после каждой сборки мусора.
И что препятствует?
То, что ты записывал в массив, не меняется произвольно,
соответственно, записываемый хендл и хешируется.
Если сборщик мусора захочет его обновить прямо в массиве,
это его личные трудности, никто не мешает сделать это правильно.
>> Ты сам это время к поиску не относишь: заполнение массива
>> занимает O(n) времени, так что O(log n) ты ни в жисть не получишь.
> Массив дан изначально, как он получен - неважно.
> К компу подсоединено внешнее устройство, которое по РС232
> рассказывает размер массива и результат сравнения двух элементов.
И?
Время передачи массива через этот канал ты сам же не учитываешь,
потому что это время --- опять не меньше O(n).
>> В каком виде он построен в задаче --- не оговорено.
> Скажика,
"Скажи-ка."
> как ты умудряешься привести фразу "Допустим, есть упорядоченный
> по возрастанию (можно и по убыванию, но здесь по возрастанию)
> массив" к наличию второго, дополнительного массива, в котором
> лежат индексы элементов с соответствующим хешем?
Ты когда-нибудь задумывался, что делается внутри обвязки к памяти?
Может, у тебя доступ к элементу массива не O(1 а ты это не учитываешь.
---
"Аллах не ведёт людей неверных."
> К поиску это не относится.
если сложность какая-нибудь O(n^n) то еще как относится...
если сложность какая-нибудь O(n^n) то еще как относится...
>> К поиску это не относится.
> если сложность какая-нибудь O(n^n) то еще как относится...
"Если б" да "кабы".
Тогда вы нагло лжёте про наличие алгоритма O(log n).
---
"Аллах не ведёт людей неверных."
> если сложность какая-нибудь O(n^n) то еще как относится...
"Если б" да "кабы".
Тогда вы нагло лжёте про наличие алгоритма O(log n).
---
"Аллах не ведёт людей неверных."
> И что препятствует?
> То, что ты записывал в массив, не меняется произвольно,
> соответственно, записываемый хендл и хешируется.
Препятствует то, что я ничего в массив не записывал, мне дали ёбанный МАССИВ ЭЛЕМЕНТОВ, ОТСОРТИРОВАННЫХ ПО ВОЗРАСТАНИЮ. Какое слово тебе непонятно?
Ты хешируешь записанный хендл (произведя над ним противоестественную операцию статик_каста к инту)? Ахуеть, сработал GC и хеш уже не соответствует хендлу. Чо делать? Я так и не услышал ответа. Между тем ситуация более чем реальная.
> Время передачи массива через этот канал ты сам же не учитываешь,
Массив не передаётся. Передаётся количество элементов и результат сравнения двух произвольных элементов. Ты на самом деле идиот, или умело прикидываешься? Сколько ещё раз мне повторять свои же слова?
> Тогда вы нагло лжёте про наличие алгоритма O(log n).
Для данного отсортированного массива элементов существует логарифмический алгоритм поиска заданного элемента. Иди на хуй.
> Может, у тебя доступ к элементу массива не O(1 а ты это не учитываешь.
Есть стандартные, СТАНДАРТНЫЕ методы оценки скорости алгоритма. Через количество доступов к памяти, через количество сравнений. Они не вполне отражают реальность со всеми её тремя уровнями кеша, но тем не менее, когда я про алгоритм говорю, что он жрёт О(ln(n я подразумеваю, что он жрёт C*ln(n) операций доступа к памяти и операций сравнения, и все, кроме охуительно упёртых тупых мудаков, почему-то меня прекрасно понимают.
Как ты думаешь, почему ты меня не понимаешь?
> То, что ты записывал в массив, не меняется произвольно,
> соответственно, записываемый хендл и хешируется.
Препятствует то, что я ничего в массив не записывал, мне дали ёбанный МАССИВ ЭЛЕМЕНТОВ, ОТСОРТИРОВАННЫХ ПО ВОЗРАСТАНИЮ. Какое слово тебе непонятно?
Ты хешируешь записанный хендл (произведя над ним противоестественную операцию статик_каста к инту)? Ахуеть, сработал GC и хеш уже не соответствует хендлу. Чо делать? Я так и не услышал ответа. Между тем ситуация более чем реальная.
> Время передачи массива через этот канал ты сам же не учитываешь,
Массив не передаётся. Передаётся количество элементов и результат сравнения двух произвольных элементов. Ты на самом деле идиот, или умело прикидываешься? Сколько ещё раз мне повторять свои же слова?
> Тогда вы нагло лжёте про наличие алгоритма O(log n).
Для данного отсортированного массива элементов существует логарифмический алгоритм поиска заданного элемента. Иди на хуй.
> Может, у тебя доступ к элементу массива не O(1 а ты это не учитываешь.
Есть стандартные, СТАНДАРТНЫЕ методы оценки скорости алгоритма. Через количество доступов к памяти, через количество сравнений. Они не вполне отражают реальность со всеми её тремя уровнями кеша, но тем не менее, когда я про алгоритм говорю, что он жрёт О(ln(n я подразумеваю, что он жрёт C*ln(n) операций доступа к памяти и операций сравнения, и все, кроме охуительно упёртых тупых мудаков, почему-то меня прекрасно понимают.
Как ты думаешь, почему ты меня не понимаешь?
>> И что препятствует?
>> То, что ты записывал в массив, не меняется произвольно,
>> соответственно, записываемый хендл и хешируется.
>> Препятствует то, что я ничего в массив не записывал,
> мне дали ёбанный МАССИВ ЭЛЕМЕНТОВ, ОТСОРТИРОВАННЫХ ПО ВОЗРАСТАНИЮ.
> Какое слово тебе непонятно?
Мне тоже дали массив элементов, отсортированных по возрастанию.
ТО, В КАКОМ ВИДЕ ХРАНИТСЯ МАССИВ, НИКОГО НЕ ПАРИТ,
и, что самое главное, время, затрачиваемое на передачу,
при оценке времени поиска _НЕ_УЧИТЫВАЕТСЯ_.
Иначе твоя оценка в O(log n) для поиска в двоичном дереве, НЕВЕРНА.
> Ты хешируешь записанный хендл (произведя над ним
> противоестественную операцию статик_каста к инту)?
> Ахуеть, сработал GC и хеш уже не соответствует хендлу.
> Чо делать? Я так и не услышал ответа. Между тем ситуация более чем реальная.
Ситуация та же: массив хранит указатели на какие-то данные,
ты передаёшь этот массив по значению, а не по ссылке.
САМ СЕБЕ ЗЛОБНЫЙ БУРАТИНО!
Это проблема не процедуры сортировки, а сборщика мусора.
Давно известная, кстати, проблема.
>> Время передачи массива через этот канал ты сам же не учитываешь,
> Массив не передаётся.
> Передаётся длина массива и результат сравнения двух произвольных элементов.
А элементы берутся из воздуха?
> Есть стандартные, СТАНДАРТНЫЕ методы оценки скорости алгоритма.
> Через количество доступов к памяти, через количество сравнений.
> Они не вполне отражают реальность со всеми её тремя уровнями кеша,
> но тем не менее, когда я про алгоритм говорю, что он жрёт О(ln(n
> я подразумеваю, что он жрёт C*ln(n) операций доступа к памяти и операций сравнения,
Есть разница между операциями доступа к _ячейке_памяти_
и к _элементу_массива_. Это может быть не одно и то же.
Ты неявно полагаешь, что ты распихал массив по элементу
на ячейку памяти, причём про _эти_ O(n) действий ты нигде
не говоришь, как и про время, им соответствующее.
> и все, кроме охуительно упёртых тупых мудаков, почему-то меня прекрасно понимают.
> Как ты думаешь, почему?
Потому что тоже когда-то вызубрили, будто массив может
кодироваться двоичной строкой исключительно последовательно,
без зазоров и без ничего больше. Magister dixit.
---
"Аллах не ведёт людей неверных."
>> То, что ты записывал в массив, не меняется произвольно,
>> соответственно, записываемый хендл и хешируется.
>> Препятствует то, что я ничего в массив не записывал,
> мне дали ёбанный МАССИВ ЭЛЕМЕНТОВ, ОТСОРТИРОВАННЫХ ПО ВОЗРАСТАНИЮ.
> Какое слово тебе непонятно?
Мне тоже дали массив элементов, отсортированных по возрастанию.
ТО, В КАКОМ ВИДЕ ХРАНИТСЯ МАССИВ, НИКОГО НЕ ПАРИТ,
и, что самое главное, время, затрачиваемое на передачу,
при оценке времени поиска _НЕ_УЧИТЫВАЕТСЯ_.
Иначе твоя оценка в O(log n) для поиска в двоичном дереве, НЕВЕРНА.
> Ты хешируешь записанный хендл (произведя над ним
> противоестественную операцию статик_каста к инту)?
> Ахуеть, сработал GC и хеш уже не соответствует хендлу.
> Чо делать? Я так и не услышал ответа. Между тем ситуация более чем реальная.
Ситуация та же: массив хранит указатели на какие-то данные,
ты передаёшь этот массив по значению, а не по ссылке.
САМ СЕБЕ ЗЛОБНЫЙ БУРАТИНО!
Это проблема не процедуры сортировки, а сборщика мусора.
Давно известная, кстати, проблема.
>> Время передачи массива через этот канал ты сам же не учитываешь,
> Массив не передаётся.
> Передаётся длина массива и результат сравнения двух произвольных элементов.
А элементы берутся из воздуха?
> Есть стандартные, СТАНДАРТНЫЕ методы оценки скорости алгоритма.
> Через количество доступов к памяти, через количество сравнений.
> Они не вполне отражают реальность со всеми её тремя уровнями кеша,
> но тем не менее, когда я про алгоритм говорю, что он жрёт О(ln(n
> я подразумеваю, что он жрёт C*ln(n) операций доступа к памяти и операций сравнения,
Есть разница между операциями доступа к _ячейке_памяти_
и к _элементу_массива_. Это может быть не одно и то же.
Ты неявно полагаешь, что ты распихал массив по элементу
на ячейку памяти, причём про _эти_ O(n) действий ты нигде
не говоришь, как и про время, им соответствующее.
> и все, кроме охуительно упёртых тупых мудаков, почему-то меня прекрасно понимают.
> Как ты думаешь, почему?
Потому что тоже когда-то вызубрили, будто массив может
кодироваться двоичной строкой исключительно последовательно,
без зазоров и без ничего больше. Magister dixit.
---
"Аллах не ведёт людей неверных."
Пошли правки задним числом.
> Как ты думаешь, почему ты меня не понимаешь?
Я тебя --- прекрасно понимаю: ты когда-то вызубрил,
что массив --- это последовательно идущие ячейки памяти.
---
"Аллах не ведёт людей неверных."
> Как ты думаешь, почему ты меня не понимаешь?
Я тебя --- прекрасно понимаю: ты когда-то вызубрил,
что массив --- это последовательно идущие ячейки памяти.
---
"Аллах не ведёт людей неверных."
и все, кроме охуительно упёртых тупых мудаков, почему-то меня прекрасно понимают.не все, а большинство.
и не понимают, а могут вообразить только однин способ организации, ибо в детстве им вбили в голову императивные языки.
[ mode]Narrowness of expirience leads to narrowness of imagination[/ mode]
> Потому что тоже когда-то вызубрили, будто массив может
> кодироваться двоичной строкой исключительно последовательно,
не вызубрили, а ввели термин. это совершенное разные вещи.
Структура данных массив, по определению, умеет:
1) доступ к элементам по ключу за O(1)
2) ключ последовательный
3) фиксированная длина
Все остальные структуры данных, это все что угодно, но не массив.
> кодироваться двоичной строкой исключительно последовательно,
не вызубрили, а ввели термин. это совершенное разные вещи.
Структура данных массив, по определению, умеет:
1) доступ к элементам по ключу за O(1)
2) ключ последовательный
3) фиксированная длина
Все остальные структуры данных, это все что угодно, но не массив.
>> Потому что тоже когда-то вызубрили, будто массив может
>> кодироваться двоичной строкой исключительно последовательно,
> не вызубрили, а ввели термин. это совершенное разные вещи.
> Структура данных массив, по определению, умеет:
> 1) делать доступ к элементам по ключу за O(1)
> 2) ключ последовательный
> 3) фиксированная длина
Моя структура умеет это всё и ещё поиск в придачу.
---
"Аллах не ведёт людей неверных."
>> кодироваться двоичной строкой исключительно последовательно,
> не вызубрили, а ввели термин. это совершенное разные вещи.
> Структура данных массив, по определению, умеет:
> 1) делать доступ к элементам по ключу за O(1)
> 2) ключ последовательный
> 3) фиксированная длина
Моя структура умеет это всё и ещё поиск в придачу.
---
"Аллах не ведёт людей неверных."
> Если б" да "кабы".
так ты можешь сказать, какая оценка алгоритма gperf или нет?
или это чисто академическое заключение, что да - такая возможность хэши построитсь есть, а на практике - как всегда все упирается в реальные ограничения (комп не бесконечно быстрый, памяти не бесконечно много и т.д.).
так ты можешь сказать, какая оценка алгоритма gperf или нет?
или это чисто академическое заключение, что да - такая возможность хэши построитсь есть, а на практике - как всегда все упирается в реальные ограничения (комп не бесконечно быстрый, памяти не бесконечно много и т.д.).
> Моя структура умеет это всё и ещё поиск в придачу.
значит она называется массив с поиском, а не массив.
значит она называется массив с поиском, а не массив.
> так ты можешь сказать, какая оценка алгоритма gperf или нет?
Не помню и не обязан помнить, поскольку в условиях настоящей
задачи это совершенно безразлично.
> на практике - как всегда все упирается в реальные ограничения
> (комп не бесконечно быстрый
Вот именно, что.
Поэтому при сильном преобладании запросов поиска перед
изменениями мой алгоритм побьёт твой. За счёт времени,
которое твой алгоритм тратит на повторные проходы по дереву.
---
"Аллах не ведёт людей неверных."
Не помню и не обязан помнить, поскольку в условиях настоящей
задачи это совершенно безразлично.
> на практике - как всегда все упирается в реальные ограничения
> (комп не бесконечно быстрый
Вот именно, что.
Поэтому при сильном преобладании запросов поиска перед
изменениями мой алгоритм побьёт твой. За счёт времени,
которое твой алгоритм тратит на повторные проходы по дереву.
---
"Аллах не ведёт людей неверных."
> Поэтому при сильном преобладании запросов поиска перед
изменениями мой алгоритм побьёт твой.
еще раз повторю, что если алгоритм хэширования gperf имеет оценку O(n^n то - нет.
поэтому еще раз спрашиваю - у тебя хоть какая-нибудь оценка его сложности есть?
сами разработчики gperf пишут
изменениями мой алгоритм побьёт твой.
еще раз повторю, что если алгоритм хэширования gperf имеет оценку O(n^n то - нет.
поэтому еще раз спрашиваю - у тебя хоть какая-нибудь оценка его сложности есть?
сами разработчики gperf пишут
The gperf utility is tuned to execute quickly, and works quickly for small to medium size data sets (around 1000 keywords). It is extremely useful for maintaining perfect hash functions for compiler keyword sets. Several recent enhancements now enable gperf to work efficiently on much larger keyword sets (over 15,000 keywords). When processing large keyword sets it helps greatly to have over 8 megs of RAM. However, since gperf does not backtrack no guaranteed solution occurs on every run. On the other hand, it is usually easy to obtain a solution by varying the option parameters. In particular, try the `-r' option, and also try changing the default arguments to the `-s' and `-j' options. To guarantee a solution, use the `-D' and `-S' options, although the final results are not likely to be a perfect hash function anymore! Finally, use the `-f' option if you want gperf to generate the perfect hash function fast, with less emphasis on making it minimal.т.е. уже где-то на миллионном массиве - нет гарантии, что ты такие хэши сможешь построить.
The size of the generate static keyword array can get extremely large if the input keyword file is large or if the keywords are quite similar. This tends to slow down the compilation of the generated C code, and greatly inflates the object code size. If this situation occurs, consider using the `-S' option to reduce data size, potentially increasing keyword recognition time a negligible amount. Since many C compilers cannot correctly generated code for large switch statements it is important to qualify the -S option with an appropriate numerical argument that controls the number of switch statements generated.
The maximum number of key positions selected for a given key has an arbitrary limit of 126. This restriction should be removed, and if anyone considers this a problem write me and let me know so I can remove the constraint.
>> Поэтому при сильном преобладании запросов поиска перед
изменениями мой алгоритм побьёт твой.
> еще раз повторю, что если алгоритм хэширования gperf имеет оценку O(n^n то - нет.
Всё "если" да "кабы". Можно подумать, что ты не из университета.
> поэтому еще раз спрашиваю - у тебя хоть какая-нибудь оценка его сложности есть?
Меня она не волнует, я уже несколько раз объяснял, почему.
---
"Три раза, Ганс, три раза.."
изменениями мой алгоритм побьёт твой.
> еще раз повторю, что если алгоритм хэширования gperf имеет оценку O(n^n то - нет.
Всё "если" да "кабы". Можно подумать, что ты не из университета.
> поэтому еще раз спрашиваю - у тебя хоть какая-нибудь оценка его сложности есть?
Меня она не волнует, я уже несколько раз объяснял, почему.
---
"Три раза, Ганс, три раза.."
Я тебя --- прекрасно понимаю: ты когда-то вызубрил,Это ты, по-моему, вызубрил именно это.
что массив --- это последовательно идущие ячейки памяти.
Массив - это набор элементов произвольной природы, в котором каждому элементу сопоставлено уникальное неотрицательное целое число, меньшее чем общее количество элементов.
interface IList
{
int GetLength;
object GetItem(int index);
}
описывает массив. Если мы говорим о сортированном массиве, то появляется дополнительный интерфейс
interface IComparable
{
int Compare(object other);
}
и гарантируется, что все элементы массива поддерживают этот интерфейс и корректно применяют Compare друг к другу.
Если ты считаешь, что за этим лежит не массив, что для того, чтобы это стало массивом, нужно произвести ещё какие действия и добавить какие-то функции (типа GetHashCode или FindElementIndexInstantly плюнь сам себе в глаз.
Да, и ещё найди какую-нибудь книжку и прочитай наконец, что понимается под выражениями вида О(n O(ln n) етс, чтобы не нести фигню по поводу долгого доступа к элементу.
int- если он ограничен 2^32 или 2^64, это какое-то убогое определение массива
В определении он не ограничен.
Однако int64 гарантированно хватит ещё лет на тридцать для _любых_ практических задач, так что при имплементации можно рассчитывать именно на него.
Кстати, ОО-модель была использована мной исключительно for convinience purposes, любой желающий может переформулировать определение в терминах ФЯ или процедурных языков.
Однако int64 гарантированно хватит ещё лет на тридцать для _любых_ практических задач, так что при имплементации можно рассчитывать именно на него.
Кстати, ОО-модель была использована мной исключительно for convinience purposes, любой желающий может переформулировать определение в терминах ФЯ или процедурных языков.
в твоей модели неявно подразумевается, что индексы элементов идут подряд.
Вообще говоря, это не всегда так.
Вообще говоря, это не всегда так.
Вообще говоря, это не всегда так.Если это заранее оговорено, то элементы могут быть нуллами. Но это тоже элементы, они учитываются в количестве элементов и на них распространяется требование применимости IComparable.Compare (в ООП по этому поводу специально делается штука вроде static int Object.Compare(object a, object b во многих ФЯ такой проблемы не стоит).
Детали реализации, вроде специальных методов хранения сильно разреженных массивов, в данном случае совершенно неважны. Хотя если углубиться в них, то обнаруживаются другие удивительные вещи, вроде автоматического появления того же log(n).
Если это заранее оговореноэто и не было заранее оговорено.
появление log(n) для чего?
> это и не было заранее оговорено.
Это всё равно не меняет того, что "контровское" другое представление подразумевает возможность захешировать объекты произвольной природы и, кстати, приложить хеш к оригинальному массиву (потому что обратно-то не восстановишь). Это как-то нифига не подходит под постановку задачи, не правда ли?
> появление log(n) для чего?
Для процедуры доступа к элементу массива. Ну вот берёшь ты, допустим, конкретную версию задачи - сортировку интов. Преобразуешь данный массив в сильно разреженный массив по индексам. А 16 гигов оперативки под рукой нет. Тогда ты свой сильно разреженный массив ужимаешь, получая, например, всего трёхкратный рост по памяти — и у тебя возникает совершенно аналогичная задача выяснения реального индекса элемента по виртуальному в этом ужатом массиве. Контра с детской непосредственностью, граничащей с откровенным слабоумием, заявляет, что для конкретных 32 или 64 битных интов O(log(n превращается в O(1).
Этот логарифм ведь вылезает из чисто математических причин - если нам нужно что-то где-то найти, у нас есть n возможных ответов, а каждое сравнение отсекает не более половины. Единственный способ избавиться от этой штуки - существенно ограничить изучаемое множество (например, сказать что мы ищем только и исключительно инт32) и заменить поиск на лукап в очень большой табличке. Подход очень клёвый, конечно, но применим далеко не всегда, поэтому исходное заявление Контры неверно для данной постановки задачи.
Это всё равно не меняет того, что "контровское" другое представление подразумевает возможность захешировать объекты произвольной природы и, кстати, приложить хеш к оригинальному массиву (потому что обратно-то не восстановишь). Это как-то нифига не подходит под постановку задачи, не правда ли?
> появление log(n) для чего?
Для процедуры доступа к элементу массива. Ну вот берёшь ты, допустим, конкретную версию задачи - сортировку интов. Преобразуешь данный массив в сильно разреженный массив по индексам. А 16 гигов оперативки под рукой нет. Тогда ты свой сильно разреженный массив ужимаешь, получая, например, всего трёхкратный рост по памяти — и у тебя возникает совершенно аналогичная задача выяснения реального индекса элемента по виртуальному в этом ужатом массиве. Контра с детской непосредственностью, граничащей с откровенным слабоумием, заявляет, что для конкретных 32 или 64 битных интов O(log(n превращается в O(1).
Этот логарифм ведь вылезает из чисто математических причин - если нам нужно что-то где-то найти, у нас есть n возможных ответов, а каждое сравнение отсекает не более половины. Единственный способ избавиться от этой штуки - существенно ограничить изучаемое множество (например, сказать что мы ищем только и исключительно инт32) и заменить поиск на лукап в очень большой табличке. Подход очень клёвый, конечно, но применим далеко не всегда, поэтому исходное заявление Контры неверно для данной постановки задачи.
> появление log(n) для чего?что есть "доступ" к элементу? чтение его значения?
Для процедуры доступа к элементу массива.
Как тут было продемонстрировано, эта операция совершенно не нужна для поиска и к поиску отношения не имеет. и приплюсовывать эти трудозатраты к затратам на СОБСТВЕННО поиск некорректно.
тут получается ситуация как в той задаче про реактивный самолёт на транспортёре.
Чтобы было всё по-честному, нужно описать вначале все ограничения и оговорки. А то как в той задаче ты всё сведёшь к тому, что мол, колёса имеют массу и момент инерции и в них можно сколь угодно много кинетической энергии закачать.
предлагаю на этом закрыть тред.
> Как тут было продемонстрировано, эта операция совершенно не нужна для поиска и к поиску отношения не имеет.
Она используется в функции "сравнить два элемента". Её основная часть используется для получения результата (собственно, индекса) в случае ужатого сильно разреженного массива (типа того, который ты описывал Мадкрозу).
> Чтобы было всё по-честному, нужно описать вначале все ограничения и оговорки.
Нет, зачем. Чтобы всё было по-честному, достаточно предварять любое утверждение, использующее более узкую трактовку условий, самой этой трактовкой. Например: "если элементы принимают значения из не очень большого дискретного множества, то можно сделать поиск за О(1 после соответствующего препроцессинга". Это действительно интересный результат, кто же спорит.
И ещё, на случай если ты тоже не знаешь, обозначение О(ln n) относится вовсе не к тактам процессора или ещё какой-нибудь фигне. Есть довольно стандартное соглашение, что считаются операции чтения, записи, сравнения, арифметические. В отдельных случаях, когда речь идёт о действительно низкоуровневой оптимизации, вроде перемножения векторов или вычисления определителя, дополнительно даются детальные оценки, сколько используется операций умножения, сколько - деления етс, но там уже никакого О(что-то там) не используется, даются конкретные числа.
Она используется в функции "сравнить два элемента". Её основная часть используется для получения результата (собственно, индекса) в случае ужатого сильно разреженного массива (типа того, который ты описывал Мадкрозу).
> Чтобы было всё по-честному, нужно описать вначале все ограничения и оговорки.
Нет, зачем. Чтобы всё было по-честному, достаточно предварять любое утверждение, использующее более узкую трактовку условий, самой этой трактовкой. Например: "если элементы принимают значения из не очень большого дискретного множества, то можно сделать поиск за О(1 после соответствующего препроцессинга". Это действительно интересный результат, кто же спорит.
И ещё, на случай если ты тоже не знаешь, обозначение О(ln n) относится вовсе не к тактам процессора или ещё какой-нибудь фигне. Есть довольно стандартное соглашение, что считаются операции чтения, записи, сравнения, арифметические. В отдельных случаях, когда речь идёт о действительно низкоуровневой оптимизации, вроде перемножения векторов или вычисления определителя, дополнительно даются детальные оценки, сколько используется операций умножения, сколько - деления етс, но там уже никакого О(что-то там) не используется, даются конкретные числа.
Ещё раз повторю. алгоритму контры не нужно иметь доступ к элементам массива. не нужно знать их значения. он не сравнивает их. скажем так: он вычисляет позицию по элементу. за O(1 если рассматривается ассимптотика только от размера массива N.
>Нет, зачем.
Затем! Что одни думают, в силу сложившейся традиции в физических задачах, считать что трения нет, блоки невесомые а нить нерастяжимая. А вот другие, ляпнув неподумав фигню, начинают с пеной у рта рассказывать что и колёса-то имеют массу и трение есть и нитки тянутся. Чтобы не выглядеть совсем уж смешно
На всякий случай скажу, что я знаю что такое O(ln(n.
>Нет, зачем.
Затем! Что одни думают, в силу сложившейся традиции в физических задачах, считать что трения нет, блоки невесомые а нить нерастяжимая. А вот другие, ляпнув неподумав фигню, начинают с пеной у рта рассказывать что и колёса-то имеют массу и трение есть и нитки тянутся. Чтобы не выглядеть совсем уж смешно
На всякий случай скажу, что я знаю что такое O(ln(n.
А 16 гигов оперативки под рукой нет.это твои личные проблемы.
вот если бы автор в посте написал:
У меня есть массив из 3 млн строк, каждая длинной в 80000, с частыми длинными префиксами....
Какой алгоритм будет самым быстрым, если у меня есть только ZilogZ80, 64кб оперативки, а элементы мне выдаются по запросу по RS-232
На всякий случай скажу, что я знаю что такое O(ln(n.+1
Кто тоже хочет узнать, спроси меня!
> Массив - это набор элементов произвольной природы, в котором каждому элементу
> сопоставлено уникальное неотрицательное целое число, меньшее чем общее количество
> элементов.
То есть, массив есть 'a с отображением a' -> 0..n.
Начнём с того, что это неправильное определение. Тем и закончим.
---
"Аллах не ведёт людей неверных."
> сопоставлено уникальное неотрицательное целое число, меньшее чем общее количество
> элементов.
То есть, массив есть 'a с отображением a' -> 0..n.
Начнём с того, что это неправильное определение. Тем и закончим.
---
"Аллах не ведёт людей неверных."
То есть, массив есть 'a с отображением a' -> 0..n.
Ты понял неправильно, перечитай пост еще раз!
Я понял правильно. Если ты считаешь иначе, доказательства за тобой.
Заодно проставь цитирование полностью, а обрезок, из которого неясно, в чём заключалось
утверждение , на которое ты ссылаешься.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
Заодно проставь цитирование полностью, а обрезок, из которого неясно, в чём заключалось
утверждение , на которое ты ссылаешься.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
То есть, массив есть 'a с отображением a' -> 0..n.А не наоборот? Я не понял, что ты написал, перечитывание не помогает.
Энивей, своё, "правильное" определение массива в студию, а потом будем сравнивать.
Ещё раз повторю. алгоритму контры не нужно иметь доступ к элементам массива. не нужно знать их значения. он не сравнивает их. скажем так: он вычисляет позицию по элементу. за O(1 если рассматривается ассимптотика только от размера массива N.При этом если речь идёт о массиве, например, строк, то доступ к массиву оказывается всё-таки нужен (для работы его гперфа либо нужен массив бесконечной длины, к чему даже сам Контра, как ни странно, относится с подозрением.
Ещё раз повторяю, утверждение "Есть алгоритм поиска за О(1)" - неверное, оно станет верным, если добавить условие "Если множество значений элементов конечно и невелико, то...", с комментарием, что понадобится довольно много дополнительной памяти.
И не нужно, пожалуйста, приплетать сюда задачу про самолёт. Исходная постановка задачи ясна как день, Контра её существенно ограничивает, я привожу контр-пример, который не удовлетворяет неявно подразумеваемым Контрой дополнительным условиям, но удовлетворяет исходной задаче. Всё.
Про 16 гигов, которых под рукой нет, было сказано в качестве иллюстрации того, как logN неявно засовывается в процедуру вычисления индекса. Если бы Контра попытался применить свой алгоритм в его базовом виде (без хешей) к int64, то ему бы потребовалось 2^64 (~10^20) байт памяти, столько не бывает, потому что не бывает никогда. Алгоритм, требующий 2^64 байт памяти не может считаться решающим что-либо. Если меня не подводит память, в солнечной системе атомов меньше, чем тут байтов.
Ещё раз, когда я начинаю говорить об int64, я НЕ ДОБАВЛЯЮ ничего к условию задачи, я беру частный случай, который демонстрирует, что алгоритм Контры не решает задачу в том виде, в каком она дана.
байт памяти, столько не бывает, потому что не бывает никогда.невесомых колёс не бывает и без трения не бывает, потому что не бывает никогда
Окей, тогда посмотри на строки.
Там объём дополнительной памяти равен где-то (количество допустимых значений символа)^(сумма символов во всех n строках).
Теперь замечу, что Контра пытается нас всех убедить, что такое представление (в виде сильно разреженного массива чудовищной длины) является "другим представлением" исходного массива, так что можно считать, что именно оно нам и дано. Ну да, теоретически является, согласен. "Взлетит".
А теперь посмотри на название этого субфорума. "Программирование", чувак! Не "абстрактная математика", не "теоретическая физика", а программирование. Математик может рассуждать о числах порядка 10^10^10 сколько ему угодно, программист всё-таки должен оставаться в здравом рассудке.
Там объём дополнительной памяти равен где-то (количество допустимых значений символа)^(сумма символов во всех n строках).
Теперь замечу, что Контра пытается нас всех убедить, что такое представление (в виде сильно разреженного массива чудовищной длины) является "другим представлением" исходного массива, так что можно считать, что именно оно нам и дано. Ну да, теоретически является, согласен. "Взлетит".
А теперь посмотри на название этого субфорума. "Программирование", чувак! Не "абстрактная математика", не "теоретическая физика", а программирование. Математик может рассуждать о числах порядка 10^10^10 сколько ему угодно, программист всё-таки должен оставаться в здравом рассудке.
программист всё-таки должен оставаться в здравом рассудке.Тогда ему не следует употреблять нотацию О-большое без оценок для констант.
Вовсе нет, коль скоро он сам остаётся в здравом рассудке и рассчитывает на здравый рассудок своих собеседников.
Обычно про эту константу что-то известно из контекста.
А в данном случае - ничего не известно, объекты какие-то сравниваются, которые хз сколько места занимают и хз насколько сложно их сравнить.
Если N умещается в int64 - то log(N)<64 и нет разницы между O(1) и O(log(N
А в данном случае - ничего не известно, объекты какие-то сравниваются, которые хз сколько места занимают и хз насколько сложно их сравнить.
Если N умещается в int64 - то log(N)<64 и нет разницы между O(1) и O(log(N
>> То есть, массив есть 'a с отображением a' -> 0..n.
> А не наоборот?
А ты всегда читаешь только середину сообщения?
Или запоминается только последняя фраза?
> Я не понял, что ты написал, перечитывание не помогает.
Исходное сообщение было такое:
F> Массив - это набор элементов произвольной природы, в котором каждому элементу
F> сопоставлено уникальное неотрицательное целое число, меньшее чем общее количество
F> элементов.
K> То есть, массив есть 'a с отображением a' -> 0..n.
K> Начнём с того, что это неправильное определение. Тем и закончим.
Мне выделять падежные окончания?
> Энивей
---
"Аллах не ведёт людей неверных."
> А не наоборот?
А ты всегда читаешь только середину сообщения?
Или запоминается только последняя фраза?
> Я не понял, что ты написал, перечитывание не помогает.
Исходное сообщение было такое:
F> Массив - это набор элементов произвольной природы, в котором каждому элементу
F> сопоставлено уникальное неотрицательное целое число, меньшее чем общее количество
F> элементов.
K> То есть, массив есть 'a с отображением a' -> 0..n.
K> Начнём с того, что это неправильное определение. Тем и закончим.
Мне выделять падежные окончания?
> Энивей
---
"Аллах не ведёт людей неверных."
> При этом если речь идёт о массиве, например, строк, то доступ к массиву оказывается всё-таки нужен
Разумеется нужен! Просто нужно произвести _одну_ выборку и всегда только одну,
а не сколько-то там в зависимости от того, как повезёт. Если используется хеширование ---
две выборки и одно сравнение на равенство, причём тоже всегда.
> если добавить условие "Если множество значений элементов конечно
Ты где-то видел бесконечные множества? Добро пожаловать в действительность!
И "с комментарием, что понадобится довольно много дополнительной памяти" можно подождать,
потому что бесплатного сыра не бывает.
И не надо играть с ограничениями, потому что я могу задать ограничения не менее реальные:
производить поиск за сколько-то мкс, нс, пс, сколько-надо-"с", а иначе умрёшь.
---
"Аллах не ведёт людей неверных."
Разумеется нужен! Просто нужно произвести _одну_ выборку и всегда только одну,
а не сколько-то там в зависимости от того, как повезёт. Если используется хеширование ---
две выборки и одно сравнение на равенство, причём тоже всегда.
> если добавить условие "Если множество значений элементов конечно
Ты где-то видел бесконечные множества? Добро пожаловать в действительность!
И "с комментарием, что понадобится довольно много дополнительной памяти" можно подождать,
потому что бесплатного сыра не бывает.
И не надо играть с ограничениями, потому что я могу задать ограничения не менее реальные:
производить поиск за сколько-то мкс, нс, пс, сколько-надо-"с", а иначе умрёшь.
---
"Аллах не ведёт людей неверных."
> программист всё-таки должен оставаться в здравом рассудке.
Скажи, почему ты тогда рассуждаешь про число операций, а не про время работы?
Может, ты считаешь, что операции сравнения равноценны?
Две выборки из памяти на каждый сравниваемый знак равноценны одной при подсчёте хеша?
Кстати, для хеширования аппаратную поддержку получить проще, чем для сравнения строк.
---
"Аллах не ведёт людей неверных."
Скажи, почему ты тогда рассуждаешь про число операций, а не про время работы?
Может, ты считаешь, что операции сравнения равноценны?
Две выборки из памяти на каждый сравниваемый знак равноценны одной при подсчёте хеша?
Кстати, для хеширования аппаратную поддержку получить проще, чем для сравнения строк.
---
"Аллах не ведёт людей неверных."
> Кстати, для хеширования аппаратную поддержку получить проще, чем для сравнения строк.
чем хэширование строки отличается от сравнения строк?
второе даже проще убрать на аппаратный уровень, т.к. хэширование зависит от задачи, а сравнение всегда одно и тоже.
чем хэширование строки отличается от сравнения строк?
второе даже проще убрать на аппаратный уровень, т.к. хэширование зависит от задачи, а сравнение всегда одно и тоже.
>> Кстати, для хеширования аппаратную поддержку получить проще, чем для сравнения строк.
чем хэширование строки отличается от сравнения строк?
Тем, что вычисляется один раз, а не сколько повезёт.
> второе даже проще убрать на аппаратный уровень, т.к. хэширование зависит от задачи,
> а сравнение всегда одно и тоже.
Двухадресный доступ сложнее одноадресного.
---
"Аллах не ведёт людей неверных."
чем хэширование строки отличается от сравнения строк?
Тем, что вычисляется один раз, а не сколько повезёт.
> второе даже проще убрать на аппаратный уровень, т.к. хэширование зависит от задачи,
> а сравнение всегда одно и тоже.
Двухадресный доступ сложнее одноадресного.
---
"Аллах не ведёт людей неверных."
а сравнение всегда одно и тоже.да, про разные кодировки и про локали благородный дон забыл
Короче. Ты можешь чётко и ясно ответить на следующие вопросы:
1) Какое определение массива ты используешь в данный момент?
2) Есть ли у тебя возможность захешировать "элемент массива" произвольной природы?
3) Как именно ты собираешься искать индекс нужного элемента в массиве строк?
4) Считаешь ли ты, что "массив строк, отсортированный по возрастанию, плюс массив их хешей, построенный за возможно экспоненциальное время или непостроенный вообще утилитой gperf" (она не гарантирует результат, если что) является другим представлением "массива строк, отсортированных по возрастанию"? Ну то есть ты можешь говорить одно, подразумевать другое? Если тебе дали спецификацию модуля в котором требуется одно, ты можешь спокойно имплементировать другое?
5) Посмотрим на гперф повнимательней. Правда ли что размер массива хешей, размер одного хеша, время сравнения двух хешей и продолжительность работы хеш-функции, построенной гперфом, не зависят от n (количества строк)?
Пятый вопрос лично мне кажется самым важным. Потому что правильный ответ на него - "нет", и, следовательно, алгоритма поиска индекса нужной строки в данном массиве, работающего за O(1 у тебя тоже нет, даже если принять все остальные оговорки.
1) Какое определение массива ты используешь в данный момент?
2) Есть ли у тебя возможность захешировать "элемент массива" произвольной природы?
3) Как именно ты собираешься искать индекс нужного элемента в массиве строк?
4) Считаешь ли ты, что "массив строк, отсортированный по возрастанию, плюс массив их хешей, построенный за возможно экспоненциальное время или непостроенный вообще утилитой gperf" (она не гарантирует результат, если что) является другим представлением "массива строк, отсортированных по возрастанию"? Ну то есть ты можешь говорить одно, подразумевать другое? Если тебе дали спецификацию модуля в котором требуется одно, ты можешь спокойно имплементировать другое?
5) Посмотрим на гперф повнимательней. Правда ли что размер массива хешей, размер одного хеша, время сравнения двух хешей и продолжительность работы хеш-функции, построенной гперфом, не зависят от n (количества строк)?
Пятый вопрос лично мне кажется самым важным. Потому что правильный ответ на него - "нет", и, следовательно, алгоритма поиска индекса нужной строки в данном массиве, работающего за O(1 у тебя тоже нет, даже если принять все остальные оговорки.
> Короче. Ты можешь чётко и ясно ответить на следующие вопросы:
Могу.
> 1) Какое определение массива ты используешь в данный момент?
Отображение конечного начального отрезка натурального ряда в заданное множество.
0..n -> 'a.
Для ускорения поиска будем хранить и частичное обратное отображение.
> 2) Есть ли у тебя возможность захешировать "элемент массива" произвольной природы?
"Произвольной" природы не бывает, элементы массива уже приведены к цифровой форме,
иначе машинной сортировки не будет.
> 3) Как именно ты собираешься искать индекс нужного элемента в массиве строк?
Применяя обратное отображение.
> 4) Считаешь ли ты, что "массив строк, отсортированный по возрастанию, плюс массив
> их хешей, построенный за возможно экспоненциальное время или непостроенный вообще
> утилитой gperf" (она не гарантирует результат, если что) является другим представлением
> "массива строк, отсортированных по возрастанию"?
Да.
> Если тебе дали спецификацию модуля в котором требуется одно, ты можешь спокойно имплементировать другое?
Если тебе дали растр, сможешь ли ты легко построить векторное представление?
> 5) Посмотрим на гперф повнимательней. Правда ли что размер массива хешей, размер
> одного хеша, время сравнения двух хешей и продолжительность работы хеш-функции,
> построенной гперфом, не зависят от n (количества строк)?
Это не важно, поскольку время хеширования не относится к поиску, оно относится
ко времени построения массива. Точно так же, как постоянно умалчиваемое тобой время
заполнения массива.
> Пятый вопрос лично мне кажется самым важным.
Пятый вопрос возникает из-за того, что ты не можешь отвлечься от мысли,
будто массив дан тебе именно в том виде, как написано в учебнике.
> Потому что правильный ответ на него - "нет",
Это неправильный ответ.
Потому что в условиях поставленной задачи, а не отвлечённого теоретизирования,
правильный ответ --- "не важно."
---
"Аллах не ведёт людей неверных."
Могу.
> 1) Какое определение массива ты используешь в данный момент?
Отображение конечного начального отрезка натурального ряда в заданное множество.
0..n -> 'a.
Для ускорения поиска будем хранить и частичное обратное отображение.
> 2) Есть ли у тебя возможность захешировать "элемент массива" произвольной природы?
"Произвольной" природы не бывает, элементы массива уже приведены к цифровой форме,
иначе машинной сортировки не будет.
> 3) Как именно ты собираешься искать индекс нужного элемента в массиве строк?
Применяя обратное отображение.
> 4) Считаешь ли ты, что "массив строк, отсортированный по возрастанию, плюс массив
> их хешей, построенный за возможно экспоненциальное время или непостроенный вообще
> утилитой gperf" (она не гарантирует результат, если что) является другим представлением
> "массива строк, отсортированных по возрастанию"?
Да.
> Если тебе дали спецификацию модуля в котором требуется одно, ты можешь спокойно имплементировать другое?
Если тебе дали растр, сможешь ли ты легко построить векторное представление?
> 5) Посмотрим на гперф повнимательней. Правда ли что размер массива хешей, размер
> одного хеша, время сравнения двух хешей и продолжительность работы хеш-функции,
> построенной гперфом, не зависят от n (количества строк)?
Это не важно, поскольку время хеширования не относится к поиску, оно относится
ко времени построения массива. Точно так же, как постоянно умалчиваемое тобой время
заполнения массива.
> Пятый вопрос лично мне кажется самым важным.
Пятый вопрос возникает из-за того, что ты не можешь отвлечься от мысли,
будто массив дан тебе именно в том виде, как написано в учебнике.
> Потому что правильный ответ на него - "нет",
Это неправильный ответ.
Потому что в условиях поставленной задачи, а не отвлечённого теоретизирования,
правильный ответ --- "не важно."
---
"Аллах не ведёт людей неверных."
> Отображение конечного начального отрезка натурального ряда в заданное множество.
> 0..n -> 'a.
Лол. Ну ты тупой =) А теперь перечитай моё определение ВНИМАТЕЛЬНО. Включая описание интерфейса доступа к массиву. Гы гы гы, тебе Красин два раза пытался намекнуть, что ты тупишь, но ты же непогрешим, my ass.
> "Произвольной" природы не бывает, элементы массива уже приведены к цифровой форме,
> иначе машинной сортировки не будет.
Элементы массива хранятся на удалённом компьютере или вообще в аналоговом устройстве. Доступ к ним осуществляется через заданное отображение. Обратного отображения не дано.
> Если тебе дали растр, сможешь ли ты легко построить векторное представление?
Если тебе дано произведение двух простых чисел в виде одного числа, сможешь ли ты легко построить это произведение в виде, собственно, произведения двух чисел? Замечу, что на гперф первым показал не я, зато я умею читать факинг мануали и прочитал там, что он строит табличку и функцию вовсе не гарантированно, так что вопрос про экспоненциальность временных затрат для данного набора элементов (и крайне продолжительного времени работы самой хеш-функции) остаётся открытым.
> Это не важно, поскольку время хеширования не относится к поиску, оно относится
> ко времени построения массива.
Мда, ты реально туповат. Поясняю: если тебе дан массив из n уникальных элементов, у тебя должно получиться как минимум n уникальных хешей, не правда ли? Тогда каждый хеш имеет длину не менее log(n и ровно столько же времени у тебя уйдёт на сравнение двух хешей (если тебе их надо сравнивать) и не меньше - на генерацию хеша по заданному элементу (который ты ищешь). Ферштейн?
> Точно так же, как постоянно умалчиваемое тобой время заполнения массива.
Я его не заполняю, мне его дают. Причём не так дают, что я его к себе в память копирую, а обеспечивают доступ к произвольному элементу и операцию сравнения. Хочешь совсем реальный пример? Их есть у меня: дана гиговая флешка, содержащая один большой файл с какими-то отсортированными небольшими записями (по килобайту, допустим). Причём подсоединена флешка по сосущему усб1.0, с его скоростью доступа в 100кБайт/с или около того. Копировать содержимое к себе и строить какое-то "другое представление" займёт очень дофига времени, почти три часа. А поиск прямо там сработает очень быстро (мне нужно будет получить и проверить не больше, чем 20 записей = 20к = 0.2 секунды).
Если тебе пример не нравится, поясни, в каком месте он не удовлетворяет исходной постановке задачи. Флешка с записями — не массив?
Если он тебе кажется совсем надуманным и нереальным, подумай о кластерах.
ЗЫ: Если массив дан не в том виде, как "написано в учебнике", то с каких же МПДХов ты считаешь его массивом? У тебя есть собственные не-учебники, в которых написано, что массив может быть дан в произвольном виде? На чём ты основываешься вообще, на своих больных фантазиях?
> 0..n -> 'a.
Лол. Ну ты тупой =) А теперь перечитай моё определение ВНИМАТЕЛЬНО. Включая описание интерфейса доступа к массиву. Гы гы гы, тебе Красин два раза пытался намекнуть, что ты тупишь, но ты же непогрешим, my ass.
> "Произвольной" природы не бывает, элементы массива уже приведены к цифровой форме,
> иначе машинной сортировки не будет.
Элементы массива хранятся на удалённом компьютере или вообще в аналоговом устройстве. Доступ к ним осуществляется через заданное отображение. Обратного отображения не дано.
> Если тебе дали растр, сможешь ли ты легко построить векторное представление?
Если тебе дано произведение двух простых чисел в виде одного числа, сможешь ли ты легко построить это произведение в виде, собственно, произведения двух чисел? Замечу, что на гперф первым показал не я, зато я умею читать факинг мануали и прочитал там, что он строит табличку и функцию вовсе не гарантированно, так что вопрос про экспоненциальность временных затрат для данного набора элементов (и крайне продолжительного времени работы самой хеш-функции) остаётся открытым.
> Это не важно, поскольку время хеширования не относится к поиску, оно относится
> ко времени построения массива.
Мда, ты реально туповат. Поясняю: если тебе дан массив из n уникальных элементов, у тебя должно получиться как минимум n уникальных хешей, не правда ли? Тогда каждый хеш имеет длину не менее log(n и ровно столько же времени у тебя уйдёт на сравнение двух хешей (если тебе их надо сравнивать) и не меньше - на генерацию хеша по заданному элементу (который ты ищешь). Ферштейн?
> Точно так же, как постоянно умалчиваемое тобой время заполнения массива.
Я его не заполняю, мне его дают. Причём не так дают, что я его к себе в память копирую, а обеспечивают доступ к произвольному элементу и операцию сравнения. Хочешь совсем реальный пример? Их есть у меня: дана гиговая флешка, содержащая один большой файл с какими-то отсортированными небольшими записями (по килобайту, допустим). Причём подсоединена флешка по сосущему усб1.0, с его скоростью доступа в 100кБайт/с или около того. Копировать содержимое к себе и строить какое-то "другое представление" займёт очень дофига времени, почти три часа. А поиск прямо там сработает очень быстро (мне нужно будет получить и проверить не больше, чем 20 записей = 20к = 0.2 секунды).
Если тебе пример не нравится, поясни, в каком месте он не удовлетворяет исходной постановке задачи. Флешка с записями — не массив?
Если он тебе кажется совсем надуманным и нереальным, подумай о кластерах.
ЗЫ: Если массив дан не в том виде, как "написано в учебнике", то с каких же МПДХов ты считаешь его массивом? У тебя есть собственные не-учебники, в которых написано, что массив может быть дан в произвольном виде? На чём ты основываешься вообще, на своих больных фантазиях?
>> Отображение конечного начального отрезка натурального ряда в заданное множество.
>> 0..n -> 'a.
> Лол. Ну ты тупой =) А теперь перечитай моё определение ВНИМАТЕЛЬНО.
Ты его перечитал?
Мне подчеркнуть падежные окончания?
> Включая описание интерфейса доступа к массиву.
Лень разбираться, что у тебя там в фигурных скобках. Слишком длинно.
Длинные определения верными не бывают.
> Гы гы гы, тебе Красин два раза пытался намекнуть, что ты тупишь,
В частности, твоё определение содержит противоречие.
>> "Произвольной" природы не бывает, элементы массива уже приведены к цифровой форме,
>> иначе машинной сортировки не будет.
> Элементы массива хранятся на удалённом компьютере или вообще в аналоговом устройстве.
Это технические детали.
> Обратного отображения не дано.
А это ограничение вообще надумано.
С этим же успехом можно положить, что после первой выборки память (удалённая машина) отключается.
>> Это не важно, поскольку время хеширования не относится к поиску, оно относится
>> ко времени построения массива.
> Мда, ты реально туповат. Поясняю: если тебе дан массив из n уникальных элементов,
> у тебя должно получиться как минимум n уникальных хешей, не правда ли?
Не "должно получиться", а "есть," ибо их создание произведено при создании массива.
>> Точно так же, как постоянно умалчиваемое тобой время заполнения массива.
> Я его не заполняю, мне его дают. Причём не так дают, что я его к себе в память копирую,
> а обеспечивают доступ к произвольному элементу и операцию сравнения.
Вот и я не создаю массив, мне его дают.
> Если тебе пример не нравится, поясни, в каком месте он не удовлетворяет исходной постановке задачи.
> Флешка с записями — не массив?
Массив.
Только специального вида, а именно такой, в котором сознательно отрезана возможность быстрого поиска,
за счёт уменьшения времени создания.
> ЗЫ: Если массив дан не в том виде, как "написано в учебнике", то с каких же МПДХов ты считаешь его массивом?
По определению.
> У тебя есть собственные не-учебники, в которых написано, что массив может быть дан в произвольном виде?
Есть куча учебников с разбором неимперативных парадигм, где рассказывается
о реализации массивов с некоторыми хорошими свойствами.
> На чём ты основываешься вообще, на своих больных фантазиях?
На определениях, не зависящих от низкоуровневых реализаций.
---
"Аллах не ведёт людей неверных."
>> 0..n -> 'a.
> Лол. Ну ты тупой =) А теперь перечитай моё определение ВНИМАТЕЛЬНО.
Ты его перечитал?
Мне подчеркнуть падежные окончания?
> Включая описание интерфейса доступа к массиву.
Лень разбираться, что у тебя там в фигурных скобках. Слишком длинно.
Длинные определения верными не бывают.
> Гы гы гы, тебе Красин два раза пытался намекнуть, что ты тупишь,
В частности, твоё определение содержит противоречие.
>> "Произвольной" природы не бывает, элементы массива уже приведены к цифровой форме,
>> иначе машинной сортировки не будет.
> Элементы массива хранятся на удалённом компьютере или вообще в аналоговом устройстве.
Это технические детали.
> Обратного отображения не дано.
А это ограничение вообще надумано.
С этим же успехом можно положить, что после первой выборки память (удалённая машина) отключается.
>> Это не важно, поскольку время хеширования не относится к поиску, оно относится
>> ко времени построения массива.
> Мда, ты реально туповат. Поясняю: если тебе дан массив из n уникальных элементов,
> у тебя должно получиться как минимум n уникальных хешей, не правда ли?
Не "должно получиться", а "есть," ибо их создание произведено при создании массива.
>> Точно так же, как постоянно умалчиваемое тобой время заполнения массива.
> Я его не заполняю, мне его дают. Причём не так дают, что я его к себе в память копирую,
> а обеспечивают доступ к произвольному элементу и операцию сравнения.
Вот и я не создаю массив, мне его дают.
> Если тебе пример не нравится, поясни, в каком месте он не удовлетворяет исходной постановке задачи.
> Флешка с записями — не массив?
Массив.
Только специального вида, а именно такой, в котором сознательно отрезана возможность быстрого поиска,
за счёт уменьшения времени создания.
> ЗЫ: Если массив дан не в том виде, как "написано в учебнике", то с каких же МПДХов ты считаешь его массивом?
По определению.
> У тебя есть собственные не-учебники, в которых написано, что массив может быть дан в произвольном виде?
Есть куча учебников с разбором неимперативных парадигм, где рассказывается
о реализации массивов с некоторыми хорошими свойствами.
> На чём ты основываешься вообще, на своих больных фантазиях?
На определениях, не зависящих от низкоуровневых реализаций.
---
"Аллах не ведёт людей неверных."
2^64 (~10^20) байт памяти, столько не бывает, потому что не бывает никогда. Алгоритм, требующий 2^64 байт памяти не может считаться решающим что-либо. Если меня не подводит память, в солнечной системе атомов меньше, чем тут байтов.Думаю, подводит - в одном моле газа их больше (то ли 23-го порядка, то ли 26).
В любом случае, представь, что каждый китаец (их больше, чем 10^9) купил по 100 литровому винту. Итого - у них всё влезет :)
> Не "должно получиться", а "есть," ибо их создание произведено при создании массива.
Пьяный что ли? Ещё раз повторяю. Есть n элементов. Уникальных элементов. Есть n хешей. Тоже уникальных. Размер каждого хеша не меньше log(n) бит. Следовательно генерация хеша по данной строке (индекс которой тебе нужно найти в массиве) занимает не меньше O(log n) операций. Потому что нужно сгенерировать log(n) бит. Понял?
> Только специального вида, а именно такой, в котором сознательно отрезана возможность быстрого поиска,
То есть ты считаешь, что в стандартное определение массива входит возможность быстрого поиска, а если такой возможности нет, то это массив специального вида? Вопросов больше не имею.
Пьяный что ли? Ещё раз повторяю. Есть n элементов. Уникальных элементов. Есть n хешей. Тоже уникальных. Размер каждого хеша не меньше log(n) бит. Следовательно генерация хеша по данной строке (индекс которой тебе нужно найти в массиве) занимает не меньше O(log n) операций. Потому что нужно сгенерировать log(n) бит. Понял?
> Только специального вида, а именно такой, в котором сознательно отрезана возможность быстрого поиска,
То есть ты считаешь, что в стандартное определение массива входит возможность быстрого поиска, а если такой возможности нет, то это массив специального вида? Вопросов больше не имею.
> да, про разные кодировки и про локали благородный дон забыл
а в hash-е их учитывать не надо что ли?
а в hash-е их учитывать не надо что ли?
Вы лучше определитесь, вы хотите решать задачу с представлением массива, которое вам хочется, любым представлением существующим в природе, гарантирующее константное время на доступ и изменение элементов, или наиболее стандартным представлением ввиде последовательных ячеек памяти. Большинство людей когда ничего не указано подразумевают последний вариант. Теоретики - второй, а люди с ником КОНТРА - первый (надо же как-то выпендриться).
в хеше обычно не надо, кроме каких-то специальных случаев
Потому что нужно сгенерировать log(n) бит. Понял?Какая разница, сколько бит, если n влезает в int64?
Большинство людей когда ничего не указано подразумевают последний вариант.Только не наши "практики". Они уже придумали какое-то аналоговое устройство хранения, доступное по сети.
Какая разница, сколько бит, если n влезает в int64?Ну уж нет, если говорить теоретически, без всяких дополнительных ограничений... :)
Тогда нельзя говорить, что доступ к массиву и сравнение элементов можно осуществить за константное время.
Тогда нельзя говорить, что доступ к массиву и сравнение элементов можно осуществить за константное время.Ну а что ж поделать? Не я первый начал какие-то странные массивы придумывать.
И не гони, кстати, мой пример с флешкой - самый что ни на есть массивистый массив. С константным временем чтения и записи. Только внешний.
да, это массив, специально сделанный таким, чтобы иметь константное время чтения и записи и, как следствие, специально сделанный таким, чтобы поиск на нём не мог быть выполнен за константное время.
Не я первый начал какие-то странные массивы придумывать.А кто?
Массив, который обеспечивает константное время выборки без дополнительных ограничений, не то что бы странный, его просто не может существовать.
> в хеше обычно не надо, кроме каких-то специальных случаев
тогда мне не понятно, как ты собрался по хэшу искать строку 'A', когда у тебя в массиве есть строка 'a', и сказано, что сравнение должно происходить с игнорированием регистра.
т.е. если сказано, что строки у нас идентичны с учетом локали, значит и хэш должен обеспечивать такую идентичность.
тогда мне не понятно, как ты собрался по хэшу искать строку 'A', когда у тебя в массиве есть строка 'a', и сказано, что сравнение должно происходить с игнорированием регистра.
т.е. если сказано, что строки у нас идентичны с учетом локали, значит и хэш должен обеспечивать такую идентичность.
Число операций, как мне кажется, ~ln(n где n-длина массива.= log n
2
Оставить комментарий
Fofa
Допустим, есть упорядоченный по возрастанию (можно и по убыванию, но здесь по возрастанию) массив. Самый быстрый из известных мне способов по поиску заданного элемента:- Влезть в середину массива: если элемент меньше серединного-оставить первую половину массива, а если больше- оставить вторую (если же все-таки это он и есть-успокоиться
-То же самое проделать с оставшейся половинкой и т.д..
Число операций, как мне кажется, ~ln(n где n-длина массива.
Кто-то знает более быстрый способ?