FirstJohn 5 мар в 08:02

Студент опроверг 40-летнюю гипотезу в информатике

Средний

5 мин

61K

Блог компании FirstVDSМатематика*

Перевод

Комментарии 45

atd 5 мар в 08:53

Уже было, причём не раз

EvilFox 6 мар в 09:36

да, https://habr.com/ru/articles/887024/

velon 5 мар в 08:53

Создаётся впечатление что статью нейросеть генерировала, один и тот же тезис из абзаца в абзац повторяется разными словами, без раскрытия деталей.

Если кратко:

Считалось что ожидаемое время вставки элемента - O(n), оказалось что - O(log(n)) - и это в худшем случае, а в лучшем так вообще O(1)

Rezzet 5 мар в 09:31

Только я так и не понял как они этого достигают, ок, не случайным поиском свободного места, а каким? Стиль статьи действительно странный, много воды и бессмысленных отсылок.

sci_nov 5 мар в 10:08

Вот здесь, но это надо разбирать, сходу непонятно.

Deosis 5 мар в 12:17

Из того, что я понял, он разбил массив на сегменты таким образом, что при вставке, если место для соответствующего хеша в первом сегменте занято, то ищем во втором.

sci_nov 5 мар в 13:09

Да. Массив из N элементов делится на непересекающиеся подмассивы, размер которых уменьшается примерно в два раза так, что всегда выполняется равенство

$N = |A_1| + |A_2| + ... + |{A}_{\lceil \log N \rceil}|.$

Дефект таков, что размер следующего подмассива равен половине предыдущего, но возможно отклонение на единицу в плюс-минус, что усложняет алгоритм. Потом на этих подмассивах организуются "пакеты" (батчи), которые завязаны на соседние подмассивы (определенное перекрытие с магическим числом 0,75). И да, при коллизии отдаем приоритет переходу к следующему хэшу нежели переходу к соседнему слоту как это делается в жадном алгоритме. В общем, нетривиальный алгоритм.

Jijiki 5 мар в 13:57

Если 16 подмассивов это 1 матрица это 4х4х4 это 1 чанк (подмассивов) кубоид (можно сделать линейный)

каждый кубик это массив

тут можно будет делать матричные преобразования над точками где эти подмассивы, в 1 матрице 16 подмассивов

sci_nov 5 мар в 14:02

У него в статье не хватает картинок, иначе путаница с подмассивами, батчами, слотами.

Jijiki 5 мар в 14:19

я понимаю, предложил воксели в представить подмассивами, а матрицу как представление 1 группы подмассивов, с матрицами работать проще, они укладываются в линейность, если на каждой точке вектора то потребуется только указатель на точку в координате 3д кубоида, соотв чанки будут не как в вокселях, а матричные в матрице 4х4 надо просто ради чанкования добавить до такого вида 4х4х4, соотв надо будет просто сохранить начальную матрицу как вид начала, все за ней 1 2 3 будут

соотв будут кубоиды со своими индексами от нуля до Н, в каждом кубоиде ячейки вида подмассив, тоесть указатель на начало, и их 4х4х4

sci_nov 5 мар в 14:21

Видимо.

Jack-Smith 7 мар в 05:55

Я так понимаю, что батчи строятся не на подмассивах, а на запросах вставки. Каждый батч забивает подмассивы Ai не больше чем на 3/4.

sci_nov 7 мар в 08:40

Видимо. Надо видео посмотреть, чуть ниже есть ссылка.

nulovkin 5 мар в 15:15

То есть впихнул туда дерево.

vkni 5 мар в 18:25

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

:-)

Jijiki 5 мар в 23:52

в матричном пермножении 100 лишних циклов даёт о себе знать внутри игры, хорошо если 15-50 циклов, а 100-200+ это уже проблемс, даже на современных, со всеми нюансами даже с учетом мощности граффического ускорителя, будет либо нагрузка на гпу, либо баланс - матрицы на процессоре, еще утилизация и снятие нагрузки с гпу )

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

поидее лучше добиться доступа по индексу это будет лучшим если есть такая возможность на нагрузке если

вопрос с анимациями на сегодняшний день до сих пор дорогие операции, так как на екране может быть Н персонажей анимированных

mayorovp 6 мар в 09:27

Какой идиот использует хеш-таблицы для хранения матриц?

wataru 6 мар в 11:25

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

segment 5 мар в 17:03

Есть еще видео https://www.youtube.com/watch?v=ArQNyOU1hyE

AndyLem 6 мар в 03:07

Потому что статьи в стиле National Geographics надо запретить. Это словесный понос, а не статья.

Wwyn 6 мар в 07:45

Или новостник из маил ру писал.

Dimly 6 мар в 09:42

Пофиг на нейросеть - когда реализация в ЯП будет, если все так кучеряво? Или патент на 25 лет и нам не видать ускорения

Quintanar 6 мар в 11:04

Какое ускорение. Это алгоритм с чисто научной пользой. На практике решает самый примитивный алгоритм линейного поиска, потому что 90+% элементов будут совсем недалеко от своего законного места (если не нужно заполнять таблицу на 100% конечно) и никакие хитрые приемы не окупятся.

Dhwtj 5 мар в 10:07

Статья максимально далека от научного стиля изложения.

Jijiki 5 мар в 10:57

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


{
  //index,
  //type,
  data
}

{
  F(key)-> index(data)
}
index logick (key) //map 128x128x128?)
{
  return index(data)  
}

Jijiki 5 мар в 11:32

она может быть на симде я понял наверно )))

Jijiki 5 мар в 10:43

не а вообще, если понаблюдать за соседними кое какими структурами то искать ниче не придётся поидее ) я даже вроде могу это доказать(как минимум может быть еще 1 структура с О(1) помимо хеш)) ), хэш таблица это функция кто мешает сразу обозначить структуру данных определенным образом и просто прыгать по ней ) там будет O(1) и поидее даже если в неё производить добавления там не играет роли конец или начало, единственный момент это поиск, но и в поиске вроде если учесть ключ и ячейку и такую структуру, к которой я клоню выше должен быть O(1) )

sci_nov 5 мар в 18:28

Кстати, неудивительно. Недавно была новость, что две девочки доказали теорему Пифагора, опираясь только на тригонометрию. И их подход признали новым. Не знаю верить ли этому, но пишут, что работа длилась 4 года... Это вам не формулы СТО выводить :)

Wesha 5 мар в 23:11

Для интересующихся: вот их доклад.

tempick 6 мар в 00:59

у меня глаза чуть не вытекли от оформления слайдов(

sergeyns 6 мар в 06:40

нда, оформление на уровне 90х...

в тот момент, когда они начинают считают площади треугольников как 1/2*высота*основание, закралось сомнение, можно ли так делать для доказательства теоремы Пифагора....

mayorovp 6 мар в 11:56

Можно. И, более того, "нормальное" доказательство тоже делает.

Только непонятно зачем тут вообще тригонометрия, если от подсчёта площади до теоремы Пифагора 1 шаг.

vkni 6 мар в 16:21

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

Wesha 6 мар в 20:42

считают площади треугольников как 1/2*высота*основание, закралось сомнение,

а зря.

Biga 6 мар в 11:46

Интересующиеся больше интересуются реализацией. Код на гитхабе есть?

Dr_Faksov 6 мар в 22:43

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

sci_nov 8 мар в 05:57

Удивительно. Вот как сомнение двигает прогресс :)

Osnovjansky 12 мар в 18:51

Не сомнение.

Просто до изобретения велосипеда (и немного после)) было принято развлекаться изобретением доказательств теоремы Пифагора.

Fragster 6 мар в 07:57

Вот уже и мемов понаделали

EvilFox 6 мар в 09:36

https://habr.com/ru/articles/887024/ по теме хэштаблиц

brightcow 6 мар в 10:35

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

sci_nov 6 мар в 10:51

Это он из будущего помог себе доказать результаты по канону)

Newbilius 6 мар в 16:09

@Boomburum а я верно понимаю, что это реклама от самого Хабра, т.е. администрация за качество услуг FirstVDS ручается? Просто из-за вашей фирменной фразы про НЛО глаз воспринимается как реклама от самого сайта, а не владельца блога)

Boomburum 6 мар в 17:58

Эта игра слов — инициатива компании FirstVDS, нативочка :)

244wet 6 мар в 16:16

совсем не плохо .

Зарегистрируйтесь на Хабре, чтобы оставить комментарий