Можно ли перечислить все элементы из коллекции, используя функцию поиска

Question

Я ищу алгоритм, возможно, эвристику для решения следующей проблемы.

Можно ли перечислить все элементы из коллекции, используя функцию поиска?Существуют ли какие-либо известные алгоритмы / эвристики для этого?

Например, согласно следующим условиям:

• Существует API, который позволяет искать песни по названию.
• Не учитывает регистр.
• Поиск соответствует любой части названия песни, он может соответствовать чему-то с начала и чему-то в середине заголовка.
• Когда поисковая фраза равна нулю, она возвращает первую верхнюю сотню.
• Песни упорядочены по свойству SongOrder.
• Возвращает только первые 100.
• Скорее всего, в базе данных будет максимум до нескольких тысяч песен.Но фактическое количество песен неизвестно потребителю функции ниже.
• Это реальная проблема, и функция поиска не может быть изменена.

Псевдо реализация поискафункция выглядит так:

List<Song> FindSongs(string searchText)
{
    var allSongs = LoadAllSongsFromDB();
    var allSongsOrderedBySongOrder = allSongs.OrderBy(x => x.SongOrder);
    var matchingSongs = allSongsInDatabase.Where(song => searchText == null || song.Title.Contains(searchText));
    var topHundred = matchingSongs.Take(100);
    return topHundred.AsList();
}

class Song
{
    public int Id;
    public string Title;
    public int SongOrder;
}

Answer 1

Если существует , равная базе данных, то лучше позволить базе данных позаботиться о фильтрации , чем выполнять фильтрацию в коде - если база данных фильтрует, ей не нужноотправляйте все песни в свой код, что экономит время, а также не перегружает сеть (представьте, что многие пользователи делают это одновременно).Базы данных также могут создавать индексы для текстовых полей (хотя они обычно не будут создавать те, которые были бы наиболее полезны для этого варианта использования), поэтому они также могут находить текст более эффективно или быстрее, чем ваш код.

Внедрение топ-100 в базу данных снова сэкономит время и сетевой трафик, поэтому мой псевдокод (смутно вдохновленный Java JPA) просто позволит базе данных выполнить всю работу:

PreparedStatement queryByTitle = myDatabase.prepareQuery(
    """SELECT * 
     FROM Songs
     WHERE title LIKE '%:partOfTitle%' 
     ORDER BY songOrder
     LIMIT 100"""
    ).withStringParameter("partOfTitle");


PreparedStatement queryWithoutTitle = myDatabase.prepareQuery(
    """SELECT * 
     FROM Songs
     ORDER BY songOrder
     LIMIT 100""")

List<Song> getSongs(String partOfTitle) {
    if (partOfTitle.isEmpty()) {
       return myConnection.executePreparedQuery(queryWithoutTitle));
    } else {
       return myConnection.executePreparedQuery(
          queryWithTitle, partOfTitle));
    }
}

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

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

1. , сохраняя список песен, отсортированных по популярности
2. , создавая три всех названий песен в gи эффективно, O (k) время поиска для длин-k частей заголовков.

Answer 2

Начните с поиска отдельных букв.Например, поиск «A», вероятно, вернет 100 песен, но поиск «Z», вероятно, вернет меньше 100.

Затем для каждой буквы, которая возвратила 100 песен, добавьте еще одну букву.Например, учитывая, что поиск «A» возвращает 100 песен, поиск «AA», «AB», «AC» и т. Д.

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