Добрый день!
Благодарствую! Огромная куча новых идей, что бы интересное рассказать. А с m&m’s вообще супер!
И как же приятно, что Вы внедряете что-то новое и полезное, да еще и с каким интересом.
Добрый день!
Если честно, запутался в Ваших рассуждениях. Если "для n-мерного объекта наличие времени свидетельствует" о наличие "как минимум в (n+1)-мерного" — тогда Вы говорите, что по времени можно добавлять координату.
Остальная часть Вашего комментария, напротив, говорит, что по времени нельзя расширять пространство.
Или я Вас не понял?
Тем не менее, не вижу ничего зазорного в расширении пространства по времени. Понятное дело, мы не можем двигаться назад во времени — это засада. Но если мы представляем время с точки зрения математики, как просто еще один параметр — где находился объект в какое-то время – то все ок.
Насчет измерения – это что-то совсем философское… Как и метр — а он определяется долью в расстоянии от одного полюса до другого — время просто показатель чего-то. И нам не важно чего. Мы измеряем время так, что-то другой по-другому. Вопрос совсем не в том, как именно мы его считаем. Даже в физике есть приспешники СГС и СИ, там либо см, либо метры… А время можно измерять и в других величинах — никто нам не запрещает, просто это неудобно.
Помимо этого существуют бесконечномерные пространства, а Вы говорите о каком-то супер-объекте с максимальной мерностью.
Насколько я помню, а я помню, в метрическом пространстве достаточно определить метрику. На этих векторах метрику определить можно. Или я что-то не понимаю?
Ну, идея была именно в том, чтобы представить многомерное пространство с совсем неординарной точки зрения :). Про Тессеракты, пересечение 4х прямых и тд — это попытка преобразовать свой мозг из 3х мерного пространства — в большее. Это доступно не всем и не совсем понятно зачем себя мучить… Я предлагаю посмотреть на мир многомерности с совершенно другой стороны — а именно как набор каких-то параметров.
Не знаю, получилось ли это донести, на это можете ответить только Вы, ибо для меня статья кажется очевидной… но это я же ее написал))
Добрый день! У Вас, вроде, неплохая статья, довольно интересно, как можно с самых азов объяснить что-то, кажущееся совсем простым, людям, не понимающим это. Правда, интересна последовательность мыслей.
Но Вы немножечко ошиблись целевой аудиторией, как по мне. На Хабре, скорее всего, нет или очень мало людей, не понимающих циклы… и маловероятно, что им будет приятно рассусоливание простейших вещей...
Если бы Вы написали статью с идеей: «Как объяснить школьнику простейшие вещи?» было бы приятнее читать, ведь так нет ощущения поучения.
Но это просто совет насчет статьи и ее преподнесения (и еще код лучше в ячейках писать, а не в скриншотах, так читабельнее).
Сама идея, которую Вы, наверное, закладывали в статью, мне нравится и интересна, но по самому Вашему докладу ее не очень просто разглядеть. Опять же, это лишь мое мнение...
Не знаю почему, но в русскоязычной литературе мало упоминаются выпуклые 3D оболочки, так что вложил чуть ли не единственную ссылку на русскоязычное описание алгоритма. (теперь помимо этой статьи :) )
Но если Вас не затрудняет чтение на английском, советую тогда лучше изучить алгоритм Чана с лучшей асимптотикой.
Спасибо, очень приятно! Да, Вы абсолютно правы — это именно Джарвис в 3D.
На всякий случай, вот ссылка на реализацию алгоритма Джарвиса в 2D. Я пробовал провести параллель между двумерным случаем и 3D, но потерпел крах, даже сам немного запутался, поэтому не стал его упоминать.
Нет, QuickHull я не писал, а Вы рекомендуете попробовать, что-то интересное? (вот ссылка на QuickHull)
Благодарю! Интересненько… Ну да, звучит очень логично. Вы не будете против, если я дополню статью Вашими данными, а то мне кажется, что именно практического применения очень не хватает в статье?
Вопрос хороший: лично я сам не сталкивался именно с использованием выпуклой оболочки, но могу предположить, где ее можно использовать. Если у Вас есть конкретные примеры, я бы с удовольствием их узнал.
Как я писал в статье, основная задача — уменьшить число рассматриваемых точек: то есть если Вам надо посчитать корреляцию каких-то величин, найти максимальные отклонения — оболочка Вам в помощь. Или если надо найти поверхность какой-то фигуры, зная некоторые точки. Я читал, что это используется в геологии для сканирования поверхностей, наверное, для определения форм тела с помощью локаторов. Но опять же, сам так не делал, так что только предполагаю, ссылаюсь на тех, кто использовал. Также читал об использовании в астрономии, для объединения некоторых тел в группы — еще одно применение. Возможно, оболочку можно использовать для 3D рисовалок.
Как по мне, алгоритм служит в основном для этих целей, но, наверняка, его можно использовать и по-другому.
Замена охватывающей сферой… ну возможно, в каких-то задачах и можно, но ведь в оболочке лежат именно точки из множества, то есть ничего лишнего. Так что если Вам важно максимальное отклонение — то, наверное, да. В случае, если Вам важно, чтобы точки были из Вашего множества, то лучше использовать именно выпуклую оболочку.
Здравствуйте! Спасибо за Ваш комментарий. Мне как раз этим и понравился алгоритм, ведь он кажется довольно сложным со стороны, но если разобраться в нем, думаешь, почему же я раньше считал, что он сложноват?
В случае четырех точек в одной плоскости алгоритм сработает в зависимости от случая. Но в общем, правильная оболочка не будет гарантироваться. Дело в том, что мы смотрим на нормаль к плоскости, и если точки 4, будет как минимум еще одна плоскость с нормалью, коллинеарной изначальной. Угол между ними нулевой, и все зависит от порядка точек, которые подаются на вход. Иначе мы можем взять не ту плоскость, а за эти последует неправильное добавление ребер и тд...
Да, Вы правы, никакой разницы, используем мы стек или очередь, нет. Что кому больше нравится. Очень интересное замечание насчет апельсина, я так не размышлял, но вроде Вы правы, получается будет как будто мы чистили апельсин овощечисткой :)
Насчет замечаний. Да, все верно, Вы правильно поняли. Спасибо, учту, добавлю описание, что массив ребер — это массив ребер, входящих в оболочку. Я просто, наверное, записался, не подумал, что это может быть по-другому.
Второе замечание тоже верно. Только там мы смотрим и на то, является ли ребро закрытым (то есть пока мы дошли в стеке до текущего ребра, возможно, обе его грани уже добавили в оболочку), и на то, какую грань, и, соответственно, какие ее ребра мы добавляем.
Я немного поменял заполняемость — поставил 70% (на 1024 элемента). В результате и впрямь испортилось, но не так сильно. Но тем не менее у меня максимум — 12 итераций, среднее 3.24
Проверил на различных числах — вот тогда все отлично. Как только начинаются повторы — тогда все ухудшается. То есть как результат: хранение различных данных — великолепно, при схожих происходит ухудшение.
Но тем не менее асимптотика O(1)...
Здравствуйте! Приятно слышать. Безусловно, с Вашими доработками код бы выглядел "сжатее" и более по C++. Но как и написано в начале статьи, эта реализация была предназначена для понимания реализации того, что происходит в хеш-таблицах. Боюсь, написание через умные указатели, добавление вектора может немного уменьшить понимаемость кода для тех, кому эта статья может помочь. А знающие программисты могут прочитать статью и вспомнить молодость :).
Вчера вечером проверил таблицу на производительность, получил слишком уж хороший результат — но было занятно посмотреть, что теория сходится с практикой. Наверное, также попробую с Вашими улучшениями и посмотрю на время выполнения, а не на количество итераций. Думаю, будет очень занятно. Может, сделаю в этой статье PS, а не, как рассчитывал, еще одну статью, все-таки не хватит материала)
Подскажите, пожалуйста, что Вы можете порекомендовать для проверки использования памяти? Пытался найти, но никак не получалось.
Очень поразил Ваш результат. Решил сам проверить, посмотреть что получится. Для упрощения генерации тестов взял целые числа. Использовал я самое простое хеширование и ту же самую реализацию, приведенную в статье. У меня все операции выполнялись с первой итерации. В 13ти случаях из ста — за две итерации. Так что либо я что-то не понимаю, может на целых числах неправильно проверять, либо что-то не так в Вашей реализации, может что-то не чистите…
В общем да, Вы абсолютно правы. Но в основном мы знаем, какие данные к нам приходят, ну или догадываемся. Тогда мы можем настроить наши хеш-функции, к примеру для строк мы можем использовать частоту использования разных букв в тексте и тд.
Так мы переходим к следующему важному пункту: почему мы должны проходить в среднем 4 элемента? Если это так, то, либо у нас на вход дается один и тот же элемент(это происходит редко), либо у нас очень плохая хеш-функция. В идеале, используя двойное хеширование, она должна раскидывать элементы по абсолютно различным местам. То есть при идеальном хешировании ключ ни для каких двух элементов не будет совпадать. Но это все теоретические предположения. На практике у нас довольно неплохая хеш-функция, и она раскидывает большинство элементов, тем не менее, конечно, коллизии есть, это бесспорно.
Также я не совсем уверен, что правильно понял Ваш первый абзац, так что на всякий случай уточняю: мы ставим не в соседний элемент, а в элемент + (результат второй хеш-функции). Так даже, если мы попали одной хеш-функцией в одну и ту же ячейку, вторая хеш-функция раскидает эти два элемента по разным ячейкам.
Что правда, то правда. Тут то же самое, что и с быстрой сортировкой и со многими другими алгоритмами. И, как и в quicksort может быть n*n, так и тут на специальных данных асимптотика может вырождаться в n. Но на обычных данных и со специально подогнанной хеш-функцией все будет хорошо. Что касается ухудшения, не совсем понял. Проблему коллизии надо как-то решать. В стандартной библиотеке используется метод цепочек, а значит, он, наверное, в среднем эффективнее. Но тем не менее метод двойного хеширования имеет вполне себе шанс на существование. Каких-то данных нет, но идея интересная, может, на днях опубликую продолжение данной статьи с исследованием времени работы.
Ко второму комментарию. Мы специально храним количество deleted-элементов, и тогда, когда их слишком много, происходит рехеш — смена ключа. Также при заполнении таблицы на 75 процентов у нас происходит resize — увеличение таблицы, что тоже не позволяет переполниться нашей таблице. Но если бы мы такое не делали, да, все было бы именно так, как Вы сказали.
Возможно, от этого статья стала бы полнее, но для понимания хеш-таблиц, или их реализации, это необязательно, мне не хотелось грузить читателей дополнительными терминами и темами, если без них можно обойтись.
Без ухода в конкретику: это бинарное дерево поиска.
Понятное дело, что хорошее дерево.
Добрый день!
Благодарствую! Огромная куча новых идей, что бы интересное рассказать. А с m&m’s вообще супер!
И как же приятно, что Вы внедряете что-то новое и полезное, да еще и с каким интересом.
Добрый день!
Если честно, запутался в Ваших рассуждениях. Если "для n-мерного объекта наличие времени свидетельствует" о наличие "как минимум в (n+1)-мерного" — тогда Вы говорите, что по времени можно добавлять координату.
Остальная часть Вашего комментария, напротив, говорит, что по времени нельзя расширять пространство.
Или я Вас не понял?
Тем не менее, не вижу ничего зазорного в расширении пространства по времени. Понятное дело, мы не можем двигаться назад во времени — это засада. Но если мы представляем время с точки зрения математики, как просто еще один параметр — где находился объект в какое-то время – то все ок.
Насчет измерения – это что-то совсем философское… Как и метр — а он определяется долью в расстоянии от одного полюса до другого — время просто показатель чего-то. И нам не важно чего. Мы измеряем время так, что-то другой по-другому. Вопрос совсем не в том, как именно мы его считаем. Даже в физике есть приспешники СГС и СИ, там либо см, либо метры… А время можно измерять и в других величинах — никто нам не запрещает, просто это неудобно.
Помимо этого существуют бесконечномерные пространства, а Вы говорите о каком-то супер-объекте с максимальной мерностью.
Не могли бы Вы пояснить?
Насколько я помню, а я помню, в метрическом пространстве достаточно определить метрику. На этих векторах метрику определить можно. Или я что-то не понимаю?
Добрый день!
Возможно, Вы правы, и такие объяснения проще — мне кажется, они примерно одинаковые по сложности.
Самое главное, Вы поняли мою идею, сам смысл статьи — я очень рад, спасибо!
Добрый день! Вы были бы правы, если бы где-то было сказано, что пространство линейное. Для метрического — все вполне себе нормально.
Ну, идея была именно в том, чтобы представить многомерное пространство с совсем неординарной точки зрения :). Про Тессеракты, пересечение 4х прямых и тд — это попытка преобразовать свой мозг из 3х мерного пространства — в большее. Это доступно не всем и не совсем понятно зачем себя мучить… Я предлагаю посмотреть на мир многомерности с совершенно другой стороны — а именно как набор каких-то параметров.
Не знаю, получилось ли это донести, на это можете ответить только Вы, ибо для меня статья кажется очевидной… но это я же ее написал))
Добрый день! У Вас, вроде, неплохая статья, довольно интересно, как можно с самых азов объяснить что-то, кажущееся совсем простым, людям, не понимающим это. Правда, интересна последовательность мыслей.
Но Вы немножечко ошиблись целевой аудиторией, как по мне. На Хабре, скорее всего, нет или очень мало людей, не понимающих циклы… и маловероятно, что им будет приятно рассусоливание простейших вещей...
Если бы Вы написали статью с идеей: «Как объяснить школьнику простейшие вещи?» было бы приятнее читать, ведь так нет ощущения поучения.
Но это просто совет насчет статьи и ее преподнесения (и еще код лучше в ячейках писать, а не в скриншотах, так читабельнее).
Сама идея, которую Вы, наверное, закладывали в статью, мне нравится и интересна, но по самому Вашему докладу ее не очень просто разглядеть. Опять же, это лишь мое мнение...
Здравствуйте!
Нашел англоязычную статью, выглядит она достойно.
Не знаю почему, но в русскоязычной литературе мало упоминаются выпуклые 3D оболочки, так что вложил чуть ли не единственную ссылку на русскоязычное описание алгоритма. (теперь помимо этой статьи :) )
Но если Вас не затрудняет чтение на английском, советую тогда лучше изучить алгоритм Чана с лучшей асимптотикой.
Спасибо, очень приятно! Да, Вы абсолютно правы — это именно Джарвис в 3D.
На всякий случай, вот ссылка на реализацию алгоритма Джарвиса в 2D. Я пробовал провести параллель между двумерным случаем и 3D, но потерпел крах, даже сам немного запутался, поэтому не стал его упоминать.
Нет, QuickHull я не писал, а Вы рекомендуете попробовать, что-то интересное? (вот ссылка на QuickHull)
Благодарю! Интересненько… Ну да, звучит очень логично. Вы не будете против, если я дополню статью Вашими данными, а то мне кажется, что именно практического применения очень не хватает в статье?
Здравствуйте!
Вопрос хороший: лично я сам не сталкивался именно с использованием выпуклой оболочки, но могу предположить, где ее можно использовать. Если у Вас есть конкретные примеры, я бы с удовольствием их узнал.
Как я писал в статье, основная задача — уменьшить число рассматриваемых точек: то есть если Вам надо посчитать корреляцию каких-то величин, найти максимальные отклонения — оболочка Вам в помощь. Или если надо найти поверхность какой-то фигуры, зная некоторые точки. Я читал, что это используется в геологии для сканирования поверхностей, наверное, для определения форм тела с помощью локаторов. Но опять же, сам так не делал, так что только предполагаю, ссылаюсь на тех, кто использовал. Также читал об использовании в астрономии, для объединения некоторых тел в группы — еще одно применение. Возможно, оболочку можно использовать для 3D рисовалок.
Как по мне, алгоритм служит в основном для этих целей, но, наверняка, его можно использовать и по-другому.
Замена охватывающей сферой… ну возможно, в каких-то задачах и можно, но ведь в оболочке лежат именно точки из множества, то есть ничего лишнего. Так что если Вам важно максимальное отклонение — то, наверное, да. В случае, если Вам важно, чтобы точки были из Вашего множества, то лучше использовать именно выпуклую оболочку.
Здравствуйте! Спасибо за Ваш комментарий. Мне как раз этим и понравился алгоритм, ведь он кажется довольно сложным со стороны, но если разобраться в нем, думаешь, почему же я раньше считал, что он сложноват?
В случае четырех точек в одной плоскости алгоритм сработает в зависимости от случая. Но в общем, правильная оболочка не будет гарантироваться. Дело в том, что мы смотрим на нормаль к плоскости, и если точки 4, будет как минимум еще одна плоскость с нормалью, коллинеарной изначальной. Угол между ними нулевой, и все зависит от порядка точек, которые подаются на вход. Иначе мы можем взять не ту плоскость, а за эти последует неправильное добавление ребер и тд...
Да, Вы правы, никакой разницы, используем мы стек или очередь, нет. Что кому больше нравится. Очень интересное замечание насчет апельсина, я так не размышлял, но вроде Вы правы, получается будет как будто мы чистили апельсин овощечисткой :)
Насчет замечаний. Да, все верно, Вы правильно поняли. Спасибо, учту, добавлю описание, что массив ребер — это массив ребер, входящих в оболочку. Я просто, наверное, записался, не подумал, что это может быть по-другому.
Второе замечание тоже верно. Только там мы смотрим и на то, является ли ребро закрытым (то есть пока мы дошли в стеке до текущего ребра, возможно, обе его грани уже добавили в оболочку), и на то, какую грань, и, соответственно, какие ее ребра мы добавляем.
Спасибо за замечания.
Ну да, достаточно требовать только для второй, правильно. Можно про запас требовать и для первой. Но Вы правы, достаточно только для второй
Я немного поменял заполняемость — поставил 70% (на 1024 элемента). В результате и впрямь испортилось, но не так сильно. Но тем не менее у меня максимум — 12 итераций, среднее 3.24
Проверил на различных числах — вот тогда все отлично. Как только начинаются повторы — тогда все ухудшается. То есть как результат: хранение различных данных — великолепно, при схожих происходит ухудшение.
Но тем не менее асимптотика O(1)...
Бесспорно, тервер не врет :)
Здравствуйте! Приятно слышать. Безусловно, с Вашими доработками код бы выглядел "сжатее" и более по C++. Но как и написано в начале статьи, эта реализация была предназначена для понимания реализации того, что происходит в хеш-таблицах. Боюсь, написание через умные указатели, добавление вектора может немного уменьшить понимаемость кода для тех, кому эта статья может помочь. А знающие программисты могут прочитать статью и вспомнить молодость :).
Вчера вечером проверил таблицу на производительность, получил слишком уж хороший результат — но было занятно посмотреть, что теория сходится с практикой. Наверное, также попробую с Вашими улучшениями и посмотрю на время выполнения, а не на количество итераций. Думаю, будет очень занятно. Может, сделаю в этой статье PS, а не, как рассчитывал, еще одну статью, все-таки не хватит материала)
Подскажите, пожалуйста, что Вы можете порекомендовать для проверки использования памяти? Пытался найти, но никак не получалось.
Так мы переходим к следующему важному пункту: почему мы должны проходить в среднем 4 элемента? Если это так, то, либо у нас на вход дается один и тот же элемент(это происходит редко), либо у нас очень плохая хеш-функция. В идеале, используя двойное хеширование, она должна раскидывать элементы по абсолютно различным местам. То есть при идеальном хешировании ключ ни для каких двух элементов не будет совпадать. Но это все теоретические предположения. На практике у нас довольно неплохая хеш-функция, и она раскидывает большинство элементов, тем не менее, конечно, коллизии есть, это бесспорно.
Также я не совсем уверен, что правильно понял Ваш первый абзац, так что на всякий случай уточняю: мы ставим не в соседний элемент, а в элемент + (результат второй хеш-функции). Так даже, если мы попали одной хеш-функцией в одну и ту же ячейку, вторая хеш-функция раскидает эти два элемента по разным ячейкам.
Ко второму комментарию. Мы специально храним количество deleted-элементов, и тогда, когда их слишком много, происходит рехеш — смена ключа. Также при заполнении таблицы на 75 процентов у нас происходит resize — увеличение таблицы, что тоже не позволяет переполниться нашей таблице. Но если бы мы такое не делали, да, все было бы именно так, как Вы сказали.