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

в 10:52, , рубрики: Алгоритмы, Компиляторы, математика, о большое, оптимизация, Программирование, структуры данных

Когда «О» большое подводит - 1

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

Память, медленная-медленная память

В начале 1980-х время, необходимое для получения данных из ОЗУ и время, необходимое для произведения вычислений с этими данными, были примерно одинаковым. Можно было использовать алгоритм, который случайно двигался по динамической памяти, собирая и обрабатывая данные. С тех пор процессоры стали производить вычисления в разы быстрее, от 100 до 1000 раз, чем получать данные из ОЗУ. Это значит, что пока процессор ждет данных из памяти, он простаивает сотни циклов, ничего не делая. Конечно, это было бы совсем глупо, поэтому современные процессоры содержат несколько уровней встроенного кэша. Каждый раз когда вы запрашиваете один фрагмент данных из памяти, дополнительные прилегающие фрагменты памяти будут записаны в кэш процессора. В итоге, при последовательном проходе по памяти можно получать к ней доступ почти настолько же быстро, насколько процессор может обрабатывать информацию, потому что куски памяти будут постоянно записываться в кэш L1. Если же двигаться по случайным адресам памяти, то зачастую кэш использовать не получится, и производительность может сильно пострадать. Если хотите узнать больше, то доклад Майка Актона на CppCon — это отличная отправная точка (и отлично проведенное время).Читать полностью »

в 7:51, , рубрики: SMAS, Алгоритмы, бинарный поиск, структуры данных, упорядоченные массивы, метки:

Вступление

Здравствуйте, читатели. Это моя первая публикация, в которой хочу поделиться структурой данных SMAS. В конце статьи будет предоставлен С++ — класс предложенной структуры данных. Реализация рекурсивная, но моя цель — донести идею. Реализацию не рекурсивной версии — дело второе. Важно «услышать» мнения.

Что не так с деревом?

Да, всё так и можно завершать статью, всем спасибо. было бы плюнуть на значительный оверхеад памяти на вспомогательные данные в виде ссылок на левые-правые поддеревья и флаг для балансировки (разный в зависимости от используемой техники — красно-чёрные, АВЛ и т.п. деревья). Ещё один, не то чтобы минус — это постоянная модификация дерева при вставке для балансировки (тут особенно важна сложность и запутанность методов для новичков). На этом минусы заканчиваются и сложно себе представить что-то лучше и более универсальное (хеш-таблицы, ИМХО, ещё круче, но ОХ УЖ ЭТИ КОЛЛИЗИИ).
Читать полностью »

в 8:00, , рубрики: big data, c++, clickhouse, columnar database, olap, open source, sql, базы данных, Блог компании Яндекс, веб-аналитика, структуры данных, яндекс

Сегодня внутренняя разработка компании Яндекс — аналитическая СУБД ClickHouse, стала доступна каждому. Исходники опубликованы на GitHub под лицензией Apache 2.0.

Яндекс открывает ClickHouse - 1

ClickHouse позволяет выполнять аналитические запросы в интерактивном режиме по данным, обновляемым в реальном времени. Система способна масштабироваться до десятков триллионов записей и петабайт хранимых данных. Использование ClickHouse открывает возможности, которые раньше было даже трудно представить: вы можете сохранять весь поток данных без предварительной агрегации и быстро получать отчёты в любых разрезах. ClickHouse разработан в Яндексе для задач Яндекс.Метрики — второй по величине системы веб-аналитики в мире.

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

Читать полностью »

в 9:44, , рубрики: c++, Программирование, структуры данных, управление памятью

Определение 1. Однородный контейнер – это такой контейнер, в котором хранятся объекты строго одного типа.

Определение 2. Неоднородный контейнер — это такой контейнер, в котором могут храниться объекты разного типа.

Определение 3. Статический контейнер — это контейнер, состав которого полностью определяется на этапе компиляции.

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

Определение 4. Динамический контейнер — это контейнер, состав которого частично или полностью определяется на этапе выполнения.

По такой классификации, очевидно, существуют четыре вида контейнеров:

  1. Статические однородные

    Сможете придумать пример?

    Обычный массив — int[n].

  2. Статические неоднородные

    Примеры?

    Наиболее яркий пример такого контейнера — это кортеж. В языке C++ он реализуется классом std::tuple<...>.

  3. Динамические однородные

    Догадались?

    Правильно, std::vector<int>.

  4. Динамические неоднородные

    Вот об этом виде контейнеров и пойдёт речь в данной статье.

Читать полностью »

в 11:47, , рубрики: php, php7, Алгоритмы, Веб-разработка, Программирование, Серверная оптимизация, структуры данных

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

Последний релиз PHP вызвал большое оживление в сообществе. Мы не могли дождаться того, чтобы начать использовать новые возможности и почувствовать вкус ~2х прироста производительности. Одна из причин, почему это случилось — структура array была переработана. Но массивы все также придерживаются принципа «оптимизировано для всего; оптимизировано для ничего», еще не все идеально, есть возможности для совершенствования.

А что насчет структур данных SPL?

К сожалению… они ужасны. Раньше, до PHP7, они предлагали _некоторые_ преимущества, но сейчас мы дошли до точки, когда использование SPL не имеет практического смысла.

Почему мы не можем просто поправить и улучшить их?

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

«SPL data structures are horribly designed.»
— Anthony Ferrara

Введение: php-ds — расширение для PHP7, добавляющее структуры данных. Этот пост кратко охватывает поведение, производительность и преимущества каждой из них. Также в конце вы найдете список ответов на ожидаемые вопросы.

Github: https://github.com/php-ds
Пространство имен: Ds
Интерфейсы: Collection, Sequence, Hashable
Классы: Vector, Deque, Stack, Queue, PriorityQueue, Map, Set
Читать полностью »

в 18:22, , рубрики: vkcup, Алгоритмы, Блог компании ВКонтакте, контест, Программирование, Спортивное программирование, структуры данных, метки:

Привет! Социальная сеть ВКонтакте возвращает свой блог на Хабр.

Первое, о чём хотим рассказать, – чемпионат по спортивному программированию VK Cup 2016 и разбор нескольких интересных задач с прошлого года.

ВКонтакте запускает третий чемпионат VK Cup - 1
Несколько слов о Чемпионате.

ВКонтакте проводит третий VK Cup — чемпионат по программированию среди русскоязычных молодых специалистов, студентов, школьников и просто любителей алгоритмов и структур данных.

К участию в нём приглашаются команды из двух человек (можно участвовать и индивидуально), чей возраст от 14 до 23 лет. Отборочные этапы пройдут с марта по май, а в финал будут приглашены лучшие 20 команд. Финал пройдет в Санкт-Петербурге в июле, лучшие восемь команд будут награждены призами:

  • 1 место — 1048576 рублей
  • 2 местo — 524288 рублей
  • 3 местo — 262144 рубля
  • 4-8 места — 131072 рубля

Соревнование будет проходить на площадке Codeforces, регистрация уже открыта — спешите зарегистрировать команду! Начать своё участие необходимо с квалификационных этапов, которые будут проходить 13-14 и 20-21 марта. Участвовать можно как в двух, так и в любом из них. Все подробности доступны по ссылке на странице Чемпионата http://codeforces.com/vkcup2016.
Читать полностью »

в 8:24, , рубрики: javascript, Алгоритмы, разработка, собеседование вопросы, структуры данных

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

image

Читать полностью »

в 10:17, , рубрики: 2-3-4 heap, 2-3-4 куча, Алгоритмы, куча, Программирование, структуры данных

Когда я первый раз столкнулся с темой бинарных деревьев в программировании, то сразу нашел на Хабре ответы почти на все возникшие у меня вопросы, но время шло, вопросов становилось больше и совсем недавно я нашел тему, которую еще не осветили на данном ресурсе — это 2-3-4 деревья. Есть отличная статья на тему 2-3 деревьев, в которой можно найти ответы на вопросы «Что такое куча?», «Что такое 2-3 деревья», а также информацию про основные операции со структурой, поэтому я не буду повторяться и сразу перейду к главной теме.

Итак, главное отличие 2-3-4 деревьев от 2-3 состоит в том, что они могут содержать более трех дочерних узлов, что дает возможность создавать четырехместные узлы (узлы, имеющие четыре дочерних узла и три элемента данных). Можно увидеть отличия визуально на гифке под эти текстом.На первом слайде показано 2-3 дерево, на втором — 2-3-4.

Структура данных 2-3-4 дерево - 1
Читать полностью »

в 10:10, , рубрики: big data, columnar database, data mining, olap, базы данных, Блог компании Яндекс, веб-аналитика, высокая производительность, структуры данных, хранение данных, яндекс, яндекс.метрика

Яндекс.Метрика сегодня это не только система веб-аналитики, но и AppMetrica — система аналитики для приложений. На входе в Метрику мы имеем поток данных — событий, происходящих на сайтах или в приложениях. Наша задача — обработать эти данные и представить их в подходящем для анализа виде.

Эволюция структур данных в Яндекс.Метрике - 1

Но обработка данных — это не проблема. Проблема в том, как и в каком виде сохранять результаты обработки, чтобы с ними можно было удобно работать. В процессе разработки нам приходилось несколько раз полностью менять подход к организации хранения данных. Мы начинали с таблиц MyISAM, использовали LSM-деревья и в конце концов пришли к column-oriented базе данных. В этой статье я хочу рассказать, что нас вынуждало это делать.

Яндекс.Метрика работает с 2008 года — более семи лет. Каждый раз изменение подхода к хранению данных было обусловлено тем, что то или иное решение работало слишком плохо — с недостаточным запасом по производительности, недостаточно надёжно и с большим количеством проблем при эксплуатации, использовало слишком много вычислительных ресурсов, или же просто не позволяло нам реализовать то, что мы хотим.
Читать полностью »

в 8:29, , рубрики: python, перевод с английского, Программирование, структуры данных

Предлагаю вашему вниманию перевод публикации Laurent Luce о реализации работы со списками в CPython. Она может быть полезна начинающим программистам на Python, либо готовящимся к собеседованию.

Эта статья описывает реализацию объекта списка в CPython, наиболее популярной реализации Python. Списки в Python — это мощный инструмент, и интересно узнать, как они устроены внутри. Взгляните на простой скрипт, который добавляет несколько целых значений в список и выводит их:

>>> l = []
>>> l.append(1)
>>> l.append(2)
>>> l.append(3)
>>> l
[1, 2, 3]
>>> for e in l:
...   print e
...
1
2
3

Как вы можете видеть, список является итерируемым объектом.

C-структура объекта списка

Объект списка в CPython представлен нижеследующей структурой в C. ob_item — это список указателей на элементы списка, allocated — количество выделенной памяти.

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

Читать полностью »

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