Различия

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

--- basics_of_algorithms:hash [2023/10/04 23:24]
werwolf [Хэш-таблицы и функция вставки]
+++ basics_of_algorithms:hash [2023/10/19 12:55] (текущий)
werwolf [Разреженные массивы]
@@ Строка 21: / Строка 21: @@
 В этом уроке мы разберемся, как устроены хэш-таблицы и как их реализовывать.
-===== Разреженные массивы =====
+===== Выводы =====
-Простейший способ определить столицу по году основания — использовать массив:
+В этом уроке мы изучили хэш-таблицы и научились с ними работать. Повторим основные тезисы:
-<code javascsript>
+  * **Хэш-таблица**  обеспечивает временную сложность . Она похожа на массив, потому что в ней тоже есть операция индексации. В качестве индекса можно использовать практически любые структуры данных — строки, дату и время, массивы.
-let capitals = [];
+  * Массивы, в которых большая часть элементов не определена, называются **разреженными**. Чтобы сэкономить память, программисты стараются уплотнить массив, но тогда довольно трудно предсказать размер массива.
+  * Остатки от деления любого числа на всегда находятся в диапазоне от до . Иногда вместо «остаток от деления на » говорят «модуль по основанию . В JavaScript и многих других языках программирования для вычисления модуля используют оператор ''%''
-capitals[881] = 'Вена';
-capitals[1237] = 'Берлин';
-capitals[1323] = 'Вильнюс';
-capitals[1614] = 'Тирана';
-capitals[1167] = 'Копенгаген';
-capitals[963] = 'Люксембург';
-capitals[1067] = 'Минск';
-capitals[1191] = 'Дублин';
-capitals[1275] = 'Амстердам';
-capitals[752] = 'Ватикан';
-capitals[1786] = 'Рейкьявик';
-capitals[1200] = 'Варшава';
-capitals[1872] = 'Будапешт';
-capitals[856] = 'Мадрид';
-capitals[1147] = 'Москва';
-</code>
-<details>
-<summary>Python</summary>
-<code python>
-capitals = [None for _ in range(1873)]
-capitals[1804] = "Вена"
-capitals[1237] = "Берлин"
-capitals[1323] = "Вильнюс"
-capitals[1614] = "Тирана"
-capitals[1167] = "Копенгаген"
-capitals[963] = "Люксембург"
-capitals[1067] = "Минск"
-capitals[1191] = "Дублин"
-capitals[1275] = "Амстердам"
-capitals[752] = "Ватикан"
-capitals[1786] = "Рейкьявик"
-capitals[1200] = "Варшава"
-capitals[1872] = "Будапешт"
-capitals[856] = "Мадрид"
-capitals[1147] = "Москва"
-</code>
-</details>
-<details>
-<summary>Java</summary>
-<code java>
-String[] capitals = new String[1873];
-capitals[881] = "Вена";
-capitals[1237] = "Берлин";
-capitals[1323] = "Вильнюс";
-capitals[1614] = "Тирана";
-capitals[1167] = "Копенгаген";
-capitals[963] = "Люксембург";
-capitals[1067] = "Минск";
-capitals[1191] = "Дублин";
-capitals[1275] = "Амстердам";
-capitals[752] = "Ватикан";
-capitals[1786] = "Рейкьявик";
-capitals[1200] = "Варшава";
-capitals[1872] = "Будапешт";
-capitals[856] = "Мадрид";
-capitals[1147] = "Москва";
-</code>
-</details>
-<details>
-<summary>PHP</summary>
-<code php>
-<?php
-$capitals = new SplFixedArray(1873);
-$capitals[881] = 'Вена';
-$capitals[1237] = 'Берлин';
-$capitals[1323] = 'Вильнюс';
-$capitals[1614] = 'Тирана';
-$capitals[1167] = 'Копенгаген';
-$capitals[963] = 'Люксембург';
-$capitals[1067] = 'Минск';
-$capitals[1191] = 'Дублин';
-$capitals[1275] = 'Амстердам';
-$capitals[752] = 'Ватикан';
-$capitals[1786] = 'Рейкьявик';
-$capitals[1200] = 'Варшава';
-$capitals[1872] = 'Будапешт';
-$capitals[856] = 'Мадрид';
-$capitals[1147] = 'Москва';
-</code>
-</details>
-Такой массив занимает много памяти. В нем хранится всего 15 городов, но при этом размер массива — это целых 1873 элемента:
-<code javascript>
-console.log(capitals.length); // => 1873
-</code>
-<details>
-<summary>Python</summary>
-<code python>
-print(len(capitals))  # => 1873
-</code>
-</details>
-<details>
-<summary>Java</summary>
-<code java>
-System.out.println(capitals.length); // => 1873
-</code>
-</details>
-<details>
-<summary>PHP</summary>
-<code php>
-<?php
-print_r(count($capitals)); // => 1873
-</code>
-</details>
-Так получилось потому, что индексами в массиве могут быть только последовательные целые числа, начиная с 0. Если мы добавляем элемент с индексом 752, в массив добавляются и неопределенные элементы с индексами от 0 до 751. Длина массива получилась равной 1873, потому что:
-  * Наибольший год основания — 1872
-  * Первым в массиве всегда стоит элемент с индексом 0
-Если мы применим массив, доступ к элементам выполнится очень быстро — за константное время   . Но при этом мы впустую расходуем память — в нашем примере массив заполнен всего на 0,8%.
-Массивы, в которых большая часть элементов не определена, называются **разреженными**. Чтобы сэкономить память, программисты стараются уплотнить массив. Скажем, в нашем примере годы находятся достаточно далеко друг от друга — на каждые двадцать пустых элементов приходится только один элемент с данными. Мы можем уменьшить массив в двадцать раз с помощью простого трюка.
-Возьмем числа 0, 1, 2 и 3, поделим их на 20 и получим такой результат:
-  *   *   *   * Целая часть этих чисел будет равна 0, пока мы не доберемся до такой операции:
-Начиная с 20, целая часть после деления будет равна 1:
-  *   * Начиная с 40, целая часть будет равна 2.
-Получается, что после преобразования числа схлопываются:
-  * От 0 до 19 → 0
-  * От 20 до 39 → 1
-  * От 40 до 59 → 2 и так далее
-Чтобы получать целую часть, воспользуемся стандартной функцией ''Math.floor'':
-<code javascript>
-let capitals = [];
-capitals[Math.floor(881 / 20)] = 'Вена';
-capitals[Math.floor(1237 / 20)] = 'Берлин';
-capitals[Math.floor(1323 / 20)] = 'Вильнюс';
-capitals[Math.floor(1614 / 20)] = 'Тирана';
-capitals[Math.floor(1167 / 20)] = 'Копенгаген';
-capitals[Math.floor(963 / 20)] = 'Люксембург';
-capitals[Math.floor(1067 / 20)] = 'Минск';
-capitals[Math.floor(1191 / 20)] = 'Дублин';
-capitals[Math.floor(1275 / 20)] = 'Амстердам';
-capitals[Math.floor(752 / 20)] = 'Ватикан';
-capitals[Math.floor(1786 / 20)] = 'Рейкьявик';
-capitals[Math.floor(1200 / 20)] = 'Варшава';
-capitals[Math.floor(1872 / 20)] = 'Будапешт';
-capitals[Math.floor(856 / 20)] = 'Мадрид';
-capitals[Math.floor(1147 / 20)] = 'Москва';
-</code>
-<details>
-<summary>Python</summary>
-<code python>
-# В Python для целых чисел используется целочисленное деление
-capitals = [None for _ in range(100)];
-capitals[1804 // 20] = "Вена"
-capitals[1237 // 20] = "Берлин"
-capitals[1323 // 20] = "Вильнюс"
-capitals[1614 // 20] = "Тирана"
-capitals[1167 // 20] = "Копенгаген"
-capitals[963 // 20] = "Люксембург"
-capitals[1067 // 20] = "Минск"
-capitals[1191 // 20] = "Дублин"
-capitals[1275 // 20] = "Амстердам"
-capitals[752 // 20] = "Ватикан"
-capitals[1786 // 20] = "Рейкьявик"
-capitals[1200 // 20] = "Варшава"
-capitals[1872 // 20] = "Будапешт"
-capitals[856 // 20] = "Мадрид"
-capitals[1147 // 20] = "Москва"
-</code>
-</details>
-<details>
-<summary>Java</summary>
-<code java>
-// В java для целых чисел используется целочисленное деление
-String[] capitals = new String[100];
-capitals[881 / 20] = "Вена";
-capitals[1237 / 20] = "Берлин";
-capitals[1323 / 20] = "Вильнюс";
-capitals[1614 / 20] = "Тирана";
-capitals[1167 / 20] = "Копенгаген";
-capitals[963 / 20] = "Люксембург";
-capitals[1067 / 20] = "Минск";
-capitals[1191 / 20] = "Дублин";
-capitals[1275 / 20] = "Амстердам";
-capitals[752 / 20] = "Ватикан";
-capitals[1786 / 20] = "Рейкьявик";
-capitals[1200 / 20] = "Варшава";
-capitals[1872 / 20] = "Будапешт";
-capitals[856 / 20] = "Мадрид";
-capitals[1147 / 20] = "Москва";
-</code>
-</details>
-<details>
-<summary>PHP</summary>
-<code php>
-<?php
-$capitals = new SplFixedArray(100);
-$capitals[round(881 / 20)] = 'Вена';
-$capitals[round(1237 / 20)] = 'Берлин';
-$capitals[round(1323 / 20)] = 'Вильнюс';
-$capitals[round(1614 / 20)] = 'Тирана';
-$capitals[round(1167 / 20)] = 'Копенгаген';
-$capitals[round(963 / 20)] = 'Люксембург';
-$capitals[round(1067 / 20)] = 'Минск';
-$capitals[round(1191 / 20)] = 'Дублин';
-$capitals[round(1275 / 20)] = 'Амстердам';
-$capitals[round(752 / 20)] = 'Ватикан';
-$capitals[round(1786 / 20)] = 'Рейкьявик';
-$capitals[round(1200 / 20)] = 'Варшава';
-$capitals[round(1872 / 20)] = 'Будапешт';
-$capitals[round(856 / 20)] = 'Мадрид';
-$capitals[round(1147 / 20)] = 'Москва';
-</code>
-</details>
-Чтобы узнать, какой город основан в 1191 году, мы проверяем элемент с индексом 1191/20:
-<code javascript>
-const getCity = (year) => capitals[Math.floor(year / 20)];
-let city = getCity(1191); // Дублин
-</code>
-<details>
-<summary>Python</summary>
-<code python>
-def get_city(year):
-    return capitals[year // 20]
-city = get_city(1191)  # Дублин
-</code>
-</details>
-<details>
-<summary>Java</summary>
-<code>
-class App {
-    public static String getCity(String[] capitals, int year) {
-        return capitals[year / 20];
-    }
-}
-</code>
-</details>
-<details>
-<summary>PHP</summary>
-<code php>
-<?php
-function getCity($year, $capitals)
-{
-    return $capitals[round($year / 20)];
-}
-</code>
-</details>
-У такого подхода есть недостаток — довольно трудно предсказать размер массива. Когда речь идет о годах основания, мы можем проанализировать данные и прикинуть, что каждые двадцать лет можно схлопнуть в один элемент.
-Для чисел 0 до 1999 нам достаточно массива из ста элементов. Последний элемент такого уплотненного массива имеет индекс 99, а ''Math.floor(1999/20)'' как раз равно 99.
-Но в другой задаче это может не сработать — например, если требуется хранить в массиве индексы, равные миллиону или миллиарду. Коэффициент 20 слишком мал для таких чисел, потому что даже уплотненный массив все равно будет слишком большим и слишком пустым.
-Но мы не можем анализировать каждую возникающую задачу. Нам бы хотелось иметь универсальный способ, подходящий для разных случаев и позволяющий контролировать размер массива. Поэтому мы рассмотрим еще один способ.
 ===== Модульная арифметика =====

Инструменты пользователя

Инструменты сайта

Различия

Инструменты страницы