Быстрая сортировка на Kotlin
Идея алгоритма
1)Выбирается опорный элемент — им может быть любой элемент массива (я в качестве опорного выбираю средний элемент массива).
2)Все остальные элементы массива сравниваются с опорным и те, которые
меньше него, ставятся слева от него, а которые больше или равны —
справа.
3)Для двух получившихся блоков массива (меньше опорного, и больше либо
равны опорному) производится точно такая же операция — выделяется
опорный элемент и всё идёт точно так же, пока в блоке не останется один
элемент.
Решил написать этот пост так как наболело. Сейчас читаю Грокаем алгоритмы, Адитья Бхаргава . А там этот алгоритм реализован на Python, ну и выглядит он классно и лаконично. Бросил себе вызов и написал на Kotlin в том же духе.
Красота же?😂
Идея алгоритма
1)Выбирается опорный элемент — им может быть любой элемент массива (я в качестве опорного выбираю средний элемент массива).
2)Все остальные элементы массива сравниваются с опорным и те, которые
меньше него, ставятся слева от него, а которые больше или равны —
справа.
3)Для двух получившихся блоков массива (меньше опорного, и больше либо
равны опорному) производится точно такая же операция — выделяется
опорный элемент и всё идёт точно так же, пока в блоке не останется один
элемент.
Решил написать этот пост так как наболело. Сейчас читаю Грокаем алгоритмы, Адитья Бхаргава . А там этот алгоритм реализован на Python, ну и выглядит он классно и лаконично. Бросил себе вызов и написал на Kotlin в том же духе.
Красота же?😂
Подсчёт суммы элементов массива через Рекурсию
Вообще эта задача тоже меня напрягла, расстроил тот факт, что в Kotlin нельзя получить срез массива, как в Python...
В Python чтобы получить список элементов массива без самого первого элемента можно написать вот так:
list[1:]
В Kotlin есть несколько вариантов:
list.takeLast(list.size - 1)
list.stream().skip(1).toList()
Не отрицаю, что есть ещё другие способы, это первое что пришло в голову.
P.S. Вообще это не повод уходить в Python, есть множество других классных концепций за которые я полюбил Kotlin
Вообще эта задача тоже меня напрягла, расстроил тот факт, что в Kotlin нельзя получить срез массива, как в Python...
В Python чтобы получить список элементов массива без самого первого элемента можно написать вот так:
list[1:]
В Kotlin есть несколько вариантов:
list.takeLast(list.size - 1)
list.stream().skip(1).toList()
Не отрицаю, что есть ещё другие способы, это первое что пришло в голову.
P.S. Вообще это не повод уходить в Python, есть множество других классных концепций за которые я полюбил Kotlin
👍2
Хеш-табли́ца
Cтруктура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение)
На картинке представлено сравнение эффективности выполнения алгоритмов с точки зрения времени выполнения операции. В худшем случае хеш-таблицы медленно выполняют все эти операции, поэтому важно избегать худшего случая быстродействия при работе с хеш-таблицами.
Для предотвращения коллизий необходимы:
- Хорошая хеш-функция
- Низкий коэффициент заполнения.
Чтобы избежать всех этих проблем с производительностью используйте уже готовые реализации структур данных, а не изобретайте свой велосипед
Почти во всех современных языках присутствуют классы, реализующие хеш-таблицы.
Java и Kotlin
HashMap — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
HashSet — реализация интерфейса множества с использованием хеш-таблицы,
LinkedHashMap — потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.
Python
dict — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
set — реализация интерфейса множества с использованием хеш-таблицы.
Подробнее почитать как работать с ними в Kotlin можно тут:
https://metanit.com/kotlin/tutorial/7.4.php
Cтруктура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение)
На картинке представлено сравнение эффективности выполнения алгоритмов с точки зрения времени выполнения операции. В худшем случае хеш-таблицы медленно выполняют все эти операции, поэтому важно избегать худшего случая быстродействия при работе с хеш-таблицами.
Для предотвращения коллизий необходимы:
- Хорошая хеш-функция
- Низкий коэффициент заполнения.
Чтобы избежать всех этих проблем с производительностью используйте уже готовые реализации структур данных, а не изобретайте свой велосипед
Почти во всех современных языках присутствуют классы, реализующие хеш-таблицы.
Java и Kotlin
HashMap — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
HashSet — реализация интерфейса множества с использованием хеш-таблицы,
LinkedHashMap — потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.
Python
dict — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
set — реализация интерфейса множества с использованием хеш-таблицы.
Подробнее почитать как работать с ними в Kotlin можно тут:
https://metanit.com/kotlin/tutorial/7.4.php
❤7