Рубрика «структура данных»

в 9:01, , рубрики: Chronicle-Map, F14, Koloboke, ruvds_статьи, simd, SmoothieMap, swisstable, uniform probing, ассоциативный массив, вставка, дерево с поворотом, красно-черное дерево, крошечные указатели, линейное зондирование, наука о данных, поиск, предельная скорость, равномерное зондирование, расширяющееся дерево, структура данных, хеш-таблицы

Более быстрые хеш-таблицы: претенденты на место SwissTable - 1


24 ноября 2021 года на сайте ArXiv.org была опубликована научная статья «Крошечные указатели» (Tiny Pointers) с описанием новой структуры данных — «крошечных» указателей, которые указывают путь к фрагменту хранимых данных и занимают меньше памяти, чем традиционные указатели.

Осенью 2021 года эту статью заметил Андрей Крапивин (Andrew Krapivin), студент Ратгерского университета в Нью-Джерси, и не придал ей особого значения, пишет Quanta Magazine, журнал о последних достижениях в математике (перевод статьи на Хабре). Только через два года он нашёл время, чтобы внимательно ознакомиться с материалом. И понял, насколько это прорывное изобретение, если применить его для оптимизации хеш-таблиц.

Данная тема уже упоминалась на Хабре, но заслуживает более подробного обсуждения.
Читать полностью »

в 18:02, , рубрики: csv, listpack, redis, Streams, потоки, Программирование, структура данных

Новая структура данных Redis 5 под названием «потоки» (streams) вызвала живой интерес в сообществе. Как-нибудь я поговорю с теми, кто использует потоки в продакшне, и напишу об этом. Но сейчас хочу рассмотреть немного другую тему. Мне начинает казаться, что многие представляют потоки неким сюрреалистичным инструментом для решения ужасно трудных задач. Действительно, эта структура данных *также* осуществляет обмен сообщениями, но будет невероятным упрощением считать, что функциональность Redis Streams ограничена только этим.

Потоки — потрясающий шаблон и «ментальная модель», которую можно с большим успехом применить в проектировании систем, но на самом деле потоки, как и большинство структур данных Redis, являются более общей структурой и могут использоваться для кучи других задач. В этой статье мы представим потоки как чистую структуру данных, полностью игнорируя блокирующие операции, группы получателей и всю остальную функциональность обмена сообщениями.
Читать полностью »

в 16:11, , рубрики: skillbox, Алгоритмы, Блог компании Skillbox, обучение, структура данных, учеба

Как я улучшил свои навыки работы с алгоритмами, структурами данных и научился использовать все это на практике - 1

От переводчика: сегодня публикуем для вас статью Фабиана Терха. Статья в первую очередь будет полезна для начинающих программистов.

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

в 16:47, , рубрики: Программирование, структура данных

В 1972 году три популярных компьютерных ученных написали книгу Структурное Программирование, где они упомянули частные неструктурированные типы:

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

(...) Такой тип называют перечислением (прим. enumeration), и мы советуем стандартную нотацию для имени типа и ассоциации имени типа с каждым из его альтернативных значений.
`
type suit = (club, diamond, heart, spade);
(...)
type year = 1900… 1960;
type coordinate = 0… 1023;
`
Читать полностью »

в 12:12, , рубрики: Алгоритмы, деревья, массив, Программирование, структура данных, метки: , ,

Здравствуйте.

Меня зовут Александр Рулёв и я хочу рассказать вам о структуре данных, на которую я совершенно случайно наткнулся (на самом деле около трёх дней перебирал возможные комбинации, пока не получил что-то однозначное).

У меня просто была проблема, которая оказалась не проблемой в реальном мире, но кажется я решил её в мире абстрактном.

Проблема была следующая: есть список элементов определённой длины. Мы должны быстро получать элемент по индексу, а так же иметь возможность вставить/удалить с любой позиции элемент. Причём чтобы остальные «пододвинулись», либо схлопнулись. Очевидно, что ни линейный список, ни массив не подходят. А обычное дерево не имеет возможности получить элемент по индексу без обхода дерева, которое тоже O(N) и лучше мы бы использовали список.

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

Асимптоматика свойственная дереву: O(log N) на все операции. Вставка/удаление в наивной реализации O((log N)^2), но мне кажется, что это можно оптимизировать.

В этой статье (первой, надеюсь не последней) я опишу, что представляет из себя это дерево, а так же как совершать над ним операции. Если всё работает так, как мне кажется и вы не найдёте никаких проблем, которые нельзя починить — мир получает прекрасную (как мне кажется) структуру данных. Иначе мне будет стыдно.
Читать полностью »

в 19:12, , рубрики: .net, особенности, строки, структура данных, метки: , ,

Строковый тип данных является одним из самых важных в любом языке программировании. Вряд ли можно написать полезную программу не задействовав этот тип данных. При этом многие разработчики не знают некоторых нюансов связанных с этим типом. Поэтому давайте рассмотрим кое-какие особенности этого типа в .NET.

Итак, начнем с представления строк в памяти

В.NET строки располагаются согласно правилу BSTR (Basic string or binary string). Данный способ представления строковых данных используется в COM (слово basic от языка программирования VisualBasic, в котором он первоначально использовался). Как известно в C/C++ для представления строк используется PWSZ, что расшифровывается как Pointer to Wide-character String, Zero-terminated. При таком расположении в памяти в конце строки находится null-терминированный символ, по которому мы можем определить конец строки. Длина строки в PWSZ ограничена лишь объемом свободной памяти. Читать полностью »

Рейтинг@Mail.ru
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js