Когда стоит использовать Jump Search

Бинарный поиск - лучше, чем Jump Search. Для чего же тогда использовать Jump Search. У него есть одно преимущество перед бинарным поиском: мы возвращаемся назад только один раз. Для бинарного поиска может потребоваться до O(logN) переходов в ситуации, когда мы захотим найти элемент, который является наименьшим или даже меньше чем наименьший.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Interpolation Sort

Имея отсортированный массив нам надо написать функцию поиска элемента. Линейный поиск сделает это за время O(n) , Jump Search - O(√ n), а бинарный за O(log n).

Поиск с интерполяцией (Interpolation Sort) является улучшением по сравнением с бинарным поиском для экземпляров, где значения в отсортированном массиве равномерно распределены.

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

Сложность выйдет O(log(log n)). О том как выбрать значения ключа, поговорим в следующем посте.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Выбор позиции для поиска в Interpolation Search

Чтобы разделить массив на две части, мы используем следующую формулу:

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]), где

A - наш искомый массив
X - элемент, который мы ищем
Lo - наименьший индекс массива
Hi - наивысший индекс массива
An - значение, хранящееся под индексом n в списке.

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

Data Science: Алгоритмы и Структуры данных | Чат 💬

Алгоритм Interpolation Search

1. В цикле вычисляем значение позиции (pos), используя формулу, что обсуждали в предпоследнем посте.

2. Если есть совпадения, то вернуть индес элемента и выйти из цикла

3. Если элемент меньше, чем позиционный элемент, вычислить положение для левого подмассива, в противном случае в правом подмассиве

4. Повторять, пока не найдется совпадение или пока подмассив не уменьшится до нуля.

Data Science: Алгоритмы и Структуры данных | Чат 💬

4 Python библиотеки для интерпретируемого машинного обучения

Yellowbrick
Эта Python библиотека и расширение пакета scikit-learn. Предоставляет некоторые полезные и симпатичные визуализации для моделей машинного обучения. Объекты визуализатора, основной интерфейс — оценки scikit-learn, поэтому если привыкли работать с scikit-learn, рабочий процесс покажется знакомым.

ELI5
Ещё одна библиотека визуализации, которая пригодится для отладки моделей машинного обучения и объяснения сделанных прогнозов. Работает с самыми распространёнными инструментами машинного обучения на Python, включая scikit-learn, XGBoost и Keras.

LIME
Расшифровывается как локальные интерпретируемые, независимые от модели объяснения. Интерпретирует предсказания, сделанные алгоритмами машинного обучения. Lime поддерживает объяснение единичных прогнозов из диапазона классификаторов, а также взаимодействует с scikit-learn «из коробки».

MLxtend
В этой библиотеке найдёте массу вспомогательных функций для машинного обучения. Она охватывает классификаторы стекинга и голосования, оценку модели, выделение признаков, а также проектирование и построение графиков.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Знакомим с разработкой и учим думать, как программист.

Подготовительный 14-дневный курс по Python для новичков 🐍

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

Вас ждет 69 уроков теории и практики прямо в браузере, вебинары, лайвкодинг и первая собственная программа на Python, написанная под руководством опытного наставника.

Начинаем 9 ноября, вы с нами?

Data Science: Алгоритмы и Структуры данных | Чат 💬

Экспоненциальный поиск или Finger Search

Finger Search ищет элемент в отстортированном массиве, перескакивая 2 ^ i элеентов на каждой итерации, где i представляет значение переменной управления циклом. После идет проверка: присутствует ли элемент поиска между последним и текущим переходом.

Как это работает?

1. Проходите по элементам массива по 2 ^ i за один раз, выполняя поиск условия:

Array[2 ^ (i - 1)] < valueWanted < Array[ 2 ^ i]


Если 2 ^ i больше, чем длина массива, установите верхнюю границу равной длине массива

2. Выполните двоичный поиск между массивами


Array[2 ^ (i - 1)] и Array[2 ^ i]

Data Science: Алгоритмы и Структуры данных | Чат 💬

Шаги решения любой задачи

Нашел статью недавно и понимаю теперь где я косячил в самом начале.

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

В статье описываются шаги того, что надо сделать приступая к любой проблеме:

1. Понять саму проблему
2. Выбрать общее направление по решению проблемы.
3. Подумайте что вы можете сделать (используя ваш предыдущий опыт)
4. Попробуйте найти, что вы не можете сделать. А также в этом кейсе подумайте и над исключительными ситуациями, которые могут произойти.
5. Только теперь подумайте над тем, что вы можете улучшить в текущем решении.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Хочешь заговорить на английском, но не с кем практиковаться?

Появилась ИИ-девушка, с которой можно общаться голосовыми на любые темы, как с носителем. Она слушает твою речь, подробно исправляет ошибки и помогает говорить увереннее. Попробовать можно бесплатно.

🇬🇧 Английский: @ChattyEnglishBot
🇩🇪 Немецкий: @ChattyGermanBot
🇪🇸 Испанский: @ChattySpanishBot
🇫🇷 Французский: @ChattyFrenchBot
🇮🇹 Итальянский: @ChattyItalianBot
🇵🇹 Португальский: @ChattyPortugueseBot
🇨🇳 Китайский: @ChattyChineseBot
🇯🇵 Японский: @ChattyJapaneseBot
🇰🇷 Корейский: @ChattyKoreanBot
🇸🇦 Арабский: @ChattyArabicBot
🇹🇷 Турецкий: @ChattyTurkishBot
🇷🇺 Русский: @ChattyRussianBot
🇵🇱 Польский: @ChattyPolandBot

Рекурсия и сортировка Quick Sort простыми словами на JavaScript

Если хотите разобраться, как устроена рекурсия и сортировка массива Quick Sort, то читайте статью ниже. В ней автор простыми словами разбирает эти алгоритмы на JavaScript.

👉Читать статью

Data Science: Алгоритмы и Структуры данных | Чат 💬

🕵 Курс "Алгоритмы и структуры данных от А до Я"

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

Длительность курса: 4 урока

Перейти к курсу

Data Science: Алгоритмы и Структуры данных | Чат 💬

​C++ - алгоритмы и структуры данных

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

🎬 Смотреть на YouTube

Data Science: Алгоритмы и Структуры данных | Чат 💬

Алгоритмы сортировки на Java с примерами

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

Наиболее популярные из них:
— сортировка пузырьком,
— быстрая сортировка,
— сортировка вставками,
— сортировка выбором.

Эти и другие алгоритмы разобрали в статье:

https://tproger.ru/articles/algoritmy-sortirovki-na-java-s-primerami/

Data Science: Алгоритмы и Структуры данных | Чат 💬

Алгоритмы поиска

Делимся статьей, где автор рассказывает про алгоритмы поиска. Ты узнаешь, зачем они нужны веб-разработчикам. Также затронута тема оценки сложности алгоритмов и Big O нотации.

Читать

Data Science: Алгоритмы и Структуры данных | Чат 💬