Присоединиться
Внутреннее соединение - это операция, которая объединяет две таблицы данных в одну таблицу на основе совпадающих значений столбцов. Простейшим способом реализации этой операции является алгоритм объединения вложенных циклов , но более масштабируемой альтернативой является алгоритм хеш-соединения .
Внедрите алгоритм «хеш-соединения» и продемонстрируйте, что он проходит тестовый сценарий, указанный ниже.
Вы должны представлять таблицы как структуры данных, которые кажутся естественными на вашем языке программирования.
Алгоритм «хеш-соединения» состоит из двух шагов:
Хэш-фаза. Создайте мультимап из одной из двух таблиц, сопоставляя их со всеми значениями столбца объединения со всеми строками, которые его содержат. Мультимап должен поддерживать хэш-ориентированный поиск, который масштабируется лучше, чем простой линейный поиск, потому что в этом весь смысл этого алгоритма. В идеале мы должны создать мультимап для меньшей таблицы, таким образом минимизируя время его создания и размер памяти. Фаза присоединения. Сканируйте другую таблицу и найдите соответствующие строки, просмотрев созданный ранее мультимап.
В псевдокоде алгоритм может быть выражен следующим образом:
пусть A = первая входная таблица (или, в идеале, большая)
пусть B = вторая входная таблица (или, в идеале, меньшая)
пусть j A = идентификатор столбца соединения таблицы A
пусть j B = идентификатор столбца соединения таблицы B
пусть M B = мультимап для отображения из отдельных значений в несколько строк таблицы B (начинается пустым)
пусть C = выходная таблица (начинается пустая)
для каждой строки b в таблице B:
место b в multimap M B под клавишей b (j B )
для каждой строки a в таблице A:
для каждой строки b в мультимадре M B под ключом a (j A ):
пусть c = конкатенация строки a и строки b
поместите строку c в таблицу C
Прецедент вход
|
Вывод
| A.Age | Имя | B.Character | B.Nemesis |
|---|---|---|---|
| 27 | Иона | Иона | Киты |
| 27 | Иона | Иона | Пауки |
| 18 | Алан | Алан | привидения |
| 18 | Алан | Алан | Zombies |
| 28 | слава | слава | Buffy |
| 28 | Алан | Алан | привидения |
| 28 | Алан | Алан | Zombies |
Порядок строк в выходной таблице не имеет значения.
Если вы используете численные индексированные массивы для представления строк таблицы (вместо обращения к столбцам по имени), вы можете представить выходные строки в форме [[27, "Jonah"], ["Jonah", "Whales"]] ,
Implement the "hash join" algorithm as a function and demonstrate that it passes the test-case listed below. The function should accept two arrays of objects and return an array of combined objects.
Input
|
Output
| A_age | A_name | B_character | B_nemesis |
|---|---|---|---|
| 27 | Jonah | Jonah | Whales |
| 27 | Jonah | Jonah | Spiders |
| 18 | Alan | Alan | Ghosts |
| 18 | Alan | Alan | Zombies |
| 28 | Glory | Glory | Buffy |
| 28 | Alan | Alan | Ghosts |
| 28 | Alan | Alan | Zombies |
The order of the rows in the output table is not significant.