1

У меня есть бинарный файл, в котором лежат одноразмерные объекты (с именем пользователя) отсортированные по имени пользователя. Есть чужой метод, который грузит весь массив в память. Моя задача в полученном из памяти массиве найти пользователя по имени.

Как мне сделать поиск бинарным поиском (или методом деления)? Я перевел искомую строку в байты, нашел середину и сравнил массивы. Как понять куда мне двигаться дальше влево или вправо? Сравнить в цикле каждый первый байт, затем каждый второй и так по всему имени и если хотя бы 1 раз левый (искомые) будет меньше правого (база), то смещать влево, т.к. список сортирован по имени? Первый раз делаю со строками... С цифровыми значениями проблем не было...

9
  • 1
    1. Что значит "одноразмерные объекты" - все объекты занимают одинаковое количество байт? 2. Если первое верно, то почему не перевести полученный массив в массив нормальных строк? После этого можно будет сравнивать строки обычным образом и работать так же, как если бы это был массив чисел.
    – rdorn
    6 июн 2018 в 21:18
  • Дело в том, что байты уже в памяти и я работаю с этой базой. Я знаю размеры объектов и они одинаковые и могу смещением достать то что мне надо. Уже часть сделана другими людьми, а конкретно передомной стоит задача сделать поиск по имени также работая только с байтами.
    – Oleg
    7 июн 2018 в 6:41
  • Если вам надо определить, присутствует ли искомая строка в каком то наборе других строк, то почему бы не воспользоваться hashset? оно искать всяко быстрее будет, чем бинарный поиск.
    – tym32167
    7 июн 2018 в 7:10
  • Не осень понял как по нему искать в моем случае.
    – Oleg
    7 июн 2018 в 7:32
  • @tym32167 там строк, в смысле string нет, их нужно сначала получить, а это будет сильно медленнее прямого поиска, да и оверхед по памяти получится в 2-3 раза.
    – rdorn
    7 июн 2018 в 7:43

3 ответа 3

1

Не понятно зачем вы переводите строку в байты, вы ведь вполне можете работать и с массивом объектов, все точно так же как с числовыми значениями, только сравниваете "Имя" например: array[index].Name > targetName строки IComparable, так что их можно сравнить на больше меньше используя метод CompareTo()

В самом простом виде поиск будет выглядеть так:

public static User BinarySearch(User[] array, string targetName) => BinarySearch(0, array.Length -1, array, target);

static User BinarySearch(int left, int right, User[] array, string targetName)
{
    if (right - left < 0) throw new Exception($"{targetName} не найден");
    var index = (right - left) / 2 + left;
    var item = array[index];
    var compareResult = item.Name.CompareTo(targetName);

    if (compareResult < 0)
        return BinarySearch(index + 1, right, array, targetName);
    if (compareResult > 0)
        return BinarySearch(left, index - 1, array, targetName);
    return item;
}

Где User это класс со свойством Name

1
  • С объектами все понятно. Но предположим что изу имя Анна, а середина попала в Аллу, значит смещаться надо влево, так как коллекция отсортированапо алфавиту. И хочу понять как это сделать красиво и правильно используя байты.
    – Oleg
    7 июн 2018 в 6:55
1

Не смотря на странность задачи, ваша идея решения верная. Нужен метод сравнения массивов, например такой:

int ByteArrayComparer(byte[] a, byte[] b)
{
  //ищем индекс не совпадающего элемента
  int i = 0;
  while(i < a.Length && i < b.Length && a[i] == b[i])
    i++;
  if(a.Length == i || b.Length == i)
  {
    //если все значения меньшего или равного по длине массива
    //совпали с соответствующими по индексам значениями большего 
    //или равного по длине массива
    return a.Length - b.Length;
  }  
  else
  {
    return a[i] - b[i];
  }
}

Результат:

  • больше нуля - массив a > массива b
  • меньше нуля - массив a < массива b
  • ноль - массивы равны

Дальше реализуете двоичный поиск как для обычного массива чисел, только вместо оператора сравнения используете этот метод и проверяете результат.


Есть и другие пути:

  • Перед поиском преобразовать исходный массив в string[] или List<string> и работать со строками. Минус - удвоенный объем памяти (или утроенный, если исходные данные в одно-байтовой кодировке). Плюс - более очевидная реализация, т.к. строки поддерживают сравнение и можно использовать обычные операторы сравнения.

  • Перед сравнением конвертировать объект из исходного массива в string и, опять же сравнение строк, для которых все уже есть, вместо сравнения массивов. Минус - постоянная генерация новых строк в процессе поиска, но расход памяти существенно меньше чем в предыдущем варианте. Плюс - аналогично предыдущему варианту.

  • Самым правильным путем было бы читать данные сразу в массив или даже HashSet строк, и поиск будет работать почти мгновенно "из коробки", но судя по вашему комментарию:

    Я все понимаю, но вот так поставлена задача. База уже в памяти и я работаю с тем, что мне дают. Грузить в память еще одну базу в объектах мне не дадут. – Oleg

    этот вариант вам не подходит.

0

Делать свою реализацию поиска объекта в массиве - дурной тон. Мы работаем на виртуальной машине и для взаимодействия с объектами нужно использовать именно её средства.

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

Учитывайте, что применять работу с множеством байт нужно только в самых крайних случаях, так как это не даст быстро получить доступ к данных в другой информационной системе, использующей иной язык программирования. Помимо этого, тот же бинарный сериализатор из стандартной библиотеки .Net в процессе работы требует одно пространство имен в месте сохранения объекта в массив байт и его последующего разбора. Это очень мешает при работе с файлом из нескольких программ.

Для поиска нужного объекта рекомендую использовать LINQ запрос. В результате поиск объекта будет реализован в одну строчку! У подобных запросов два варианта написания: SQL-подобный синтаксис или с вызовом методов перечислений, добавленных через расширение. Лично мне больше нравится последний. Кроме того, эти запросы можно легко через Entity Framework подключить к базе данных, а она-то точно найдет объект быстрее.

1
  • Я все понимаю, но вот так поставлена задача. База уже в памяти и я работаю с тем, что мне дают. Грузить в память еще одну базу в объектах мне не дадут.
    – Oleg
    7 июн 2018 в 6:45

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.