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

в 20:17, , рубрики: Коллекции .NET, сложность алгоритмов, структуры данных

  1. Нотация О большое для оценки сложности алгоритмов

  2. Структуры данных и их применение в алгоритмах

  3. Некоторые рекомендации для разработки на .NET

При написании алгоритмов нужно учитывать их масштабируемость. Для этих целей используется понятие «О большое», представленное Паулем Бахманном в 1894 году для того, чтобы приблизительно оценивать, как время выполнения алгоритма будет расти при увеличении размеров входных данных.

Пусть f(n) — время выполнения алгоритма, а g(n)  - временная сложность, которая проверяется для алгоритма. Тогда f(n)=O(g(n))Читать полностью »

в 9:01, , рубрики: cassandra, CedarDB, DuckDB, dynamodb, imdb, LeanStore, mongodb, mysql, NVMe, OrioleDB, pcie, postgresql, PostgreSQL 17, redis, ruvds_статьи, SATA, spdk, sqlite, ssd, TPC-DS, TPC-H, UmbraDB, Valkey, резидентная БД, соединение хеш-таблиц, структуры данных
Почему СУБД такие медленные - 1

Недавно на Хабре публиковался перевод статьи «Просто выберите Postgres» (оригинал, англ. яз) с аргументами, что Postgres — оптимальная БД для десктопных и мобильных приложений. Аналогичное мнение высказывают в других популярных статьях вроде «До свидания MongoDB, здравствуй PostgreSQL». Главным недостатком SQLite называют то, что данные хранятся в одном файле, а MongoDB (а также DynamoDB и Cassandra) — низкую производительность:

«Всё это связано с тем, что подобные базы данных, по сути, представляют собой огромную распределённую хеш-таблицу. Единственные операции, работающие без необходимости сканирования всей базы данных — это поиск по секционному ключу и сканы, при которых используется ключ сортировки.

…Если паттерны доступа существенно изменятся, то может потребоваться полная повторная обработка всех данных».

Более производительные резидентные БД хранят данные в памяти (Redis, Valkey), но их использование ограничено объёмом ОЗУ.

После такого заявления интересно посмотреть на независимые тесты производительности разных СУБД.Читать полностью »

в 13:00, , рубрики: concurrency, ruvds_переводы, конкурентность, Параллелизм, параллельные вычисления, структуры данных, тестирование

Как правильно тестировать конкурентные структуры данных - 1


Есть потрясающая библиотека Rust под названием loom, которую можно использовать для тщательного тестирования неблокируемых (lock-free) структур данных. Я давно хотел разобраться, как она работает. И сейчас хочу! Но недавно я случайно реализовал небольшой эксперимент, который, как мне кажется, содержит часть идей loom, поэтому о нём стоит написать. Моя цель — не научить вас тому, что нужно использовать на практике (если вы хотите этого, то почитайте документацию loom), а, скорее, вывести пару идей из фундаментальных принципов.Читать полностью »

в 8:01, , рубрики: algorithms, bloom filter, data structures, javascript, timeweb_статьи_перевод, Алгоритмы, структуры данных, фильтр блума
Фильтр Блума - 1

У каждого разработчика есть набор инструментов для решения различных задач. Однако со временем возникает необходимость расширять этот набор, чтобы эффективно справляться с более сложными задачами. В этой статье я хочу познакомить вас с инструментом, которым вы, скорее всего, раньше не пользовались. И хотя он подходит для решения узкого спектра задач, его использование может оказаться весьма полезным. Знакомьтесь — "фильтр Блума" (Bloom filter).

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

в 13:00, , рубрики: Google, ruvds_переводы, Алгоритмы, задачи на собеседованиях, собеседование в google, собеседования, структуры данных, техническое собеседование

Мой опыт собеседования в Google [оффер на L5] - 1


Предупреждение: я не смогу привести в статье конкретные вопросы из-за подписанного соглашения о неразглашении (NDA).

Работая в лондонском офисе Facebook в команде Instagram*, я начал задумываться о возвращении в Индию. В ноябре 2022 года со мной связался рекрутер Google. Он сообщил об открытии в Бангалоре должности уровня L5 и спросил, интересно ли мне это.

Так как я уже раздумывал о переезде в Индию, то ранее собеседовался в Google, но мне предложили более низкую должность (L4), чем я хотел; потом я устроился в META* на уровень E5.

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

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

На этот раз в процессе подготовки возникла уникальная для меня сложность — счастливое пополнение в моей семье, дочка. За моё внимание боролись подгузники и кодинг, было очень сложно выделить время на сосредоточенную подготовку! У меня было примерно 25-30 дней на освоение и искусства ухода за ребёнком, и прохождения собеседования.Читать полностью »

в 13:00, , рубрики: ruvds_перевод, small string optimisation, string, строки, строковые типы, структуры данных

Собственный строковый тип на Rust - 1


Писать компиляторы — моё хобби, ничего не могу с собой поделать. Поэтому я пишу и много парсеров. В программировании систем обычно лучше попытаться сделать память общей, чем использовать её многократно, поэтому мои типы AST обычно выглядят так.

pub enum Expr<'src> {
  Int(u32)
  Ident(&'src str),
  // ...
}

Когда мы парсим идентификатор, то вместо копирования его названия в новую String мы заимствуем его из входной исходной строки. Это позволяет избежать дополнительных распределений, дополнительного копирования и экономит слово на представлении данных. Компиляторы могут быть очень требовательны к памяти, поэтому стоит выбирать краткое представление.
Читать полностью »

в 13:00, , рубрики: c++, data structures, ruvds_перевод, vscode, Алгоритмы, Блог компании RUVDS.com, красно-черные деревья, Программирование, структуры данных, текстовые редакторы, хранение данных

Выбор структур данных для самописного текстового редактора - 1


Программирование текстовых редакторов может быть очень интересной и сложной задачей. Типы задач, которые должны решать текстовые редакторы, варьируются от тривиальных до невероятно трудных. Недавно я занимался переработкой внутренних структур данных редактора, над которым я работаю. В частности, самой фундаментальной для любого текстового редактора структуры данных: текста.

Ресурсы

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

  • Build Your Own Text Editor — наверно, самый фундаментальный пост о создании текстового редактора с нуля, который я видел. Это превосходный туториал на случай, если вы хотите начать писать собственный текстовый редактор. Стоит заметить, что в редакторе из этого туториала в качестве внутренней структуры для текста используется, по сути, вектор строк.
  • Text Editor: Data Structures — отличный обзор множества структур данных, которые можно использовать при реализации текстового редактора. (Спойлер: как минимум одна из них будет рассмотрена в моём посте)
  • Плейлист Ded (Text Editor) на YouTube — это потрясающая серия, в которой @tscoding фиксирует процесс создания с нуля текстового редактора. Эти видео стали для меня источником вдохновения.

Зачем?

Если в сети есть так много хороших ресурсов о создании собственного текстового редактора (не говоря уже о том, что уже существует множество феноменальных текстовых редакторов), то зачем я это пишу? На то есть несколько причин:

  1. Я хотел заняться проектом, непохожим ни на один свой прошлый.
  2. Я хотел создать инструмент, которым смогу пользоваться.
  3. Мне всегда хотелось глубже разобраться с созданием собственных структур данных.

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

в 13:16, , рубрики: decorator, python, Алгоритмы, декоратор, классы, ооп, Программирование, структуры данных, Читальный зал
6 Python декораторов, которые значительно упростят ваш код - 1

"Простое лучше сложного".

Лучшая функция Python, которая применяет эту философию из "дзен Python", - это декоратор.

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

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

в 5:34, , рубрики: c++, Алгоритмы, жюри олимпиады, составление задач, Спортивное программирование, структуры данных

Меня зовут Абай Баймуканов, я – разработчик-алгоритмист. Уже несколько лет увлекаюсь олимпиадными программированием, поэтому в этой статье хотел бы поделиться своим видением по этому поводу.

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

в 23:02, , рубрики: .net, C#, алгоритм, алгоритм краскала, Алгоритмы, графы, Краскала, математика, минимальное остовное дерево, Программирование, реализация, система непересекающихся множеств, сортировка графа, структуры данных, хранение информации

В данной статье для реализации алгоритма будут рассмотрены:

  1. Система хранения графа на основе List<>

  2. Сортировка рёбер графа по весу

  3. Система непересекающихся множеств

Алгоритм Краскала необходим для нахождения минимального остовного дерева графа.

О чём речь?

Если прочитав предложение выше вы невольно задались этим вопросом, то вам следует изучить пару книг по теории графов информацию, представленную в этом блоке.

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