Как я обнаружил, что C# SortedList использует двоичный поиск и почему вам это важно

1656529813 kak ya obnaruzhil chto c sortedlist ispolzuet dvoichnyj poisk i

автора Рина Арстейн

Есть давние дебаты: могут ли программисты обойтись только знанием кода? Или им следует понимать некоторые внутренние структуры, основные структуры данных и алгоритмы поиска/сортировки?

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

1*wnTXS4cPw-Tw_oC79VweTQ

Обзор системы

Представьте систему представителей обслуживания клиентов, где каждый пользователь пишет заметки для отслеживания действий и разговоров с клиентами. Если примечание требует дальнейших действий, пользователь может добавить срок выполнения для определенной даты и времени, и это станет «задачей». В любой момент пользователь может обозначить задание как «выполненное», и задание будет удалено, оставаясь в списке примечаний.

Для удобного доступа все заметки отображаются в порядке убывания по дате вставки (сначала самая старая заметка). Задания отображаются в порядке возрастания по дате выполнения (сначала будущие/просроченные задачи).

Как обычно, часть сложности исходной системы опущена для простоты (постоянство, многопоточность и т.п.). Я также включил ссылку на GitHub с рабочей версией кода, включенной в эту публикацию. Вы можете запустить его для себя. (Это внизу сообщения, поэтому даже если вы не читаете его, вам придется прокрутить весь путь вниз, ха!).

Реализация

Начнем с определения класса Note:

Это обычный объект данных.

Далее мы создадим класс NotesManager, содержащий все заметки/задания и управляющий доступом к ним:

Класс NotesManager использует SortedList для сохранения заметок/заданий в правильном порядке, определенном типом списка и SortDirection, предоставленными NoteComparer. Заметки упорядочиваются по дате InsertDate по возрастанию, а задача – по дате выполнения, по убыванию. Класс NotesManager заботится о создании NoteIndex с правильной датой. Он вставляет заметку в соответствующий список.

Последняя функция, которая нам нужна, — обозначить задачу как «выполненную», которая затем удаляет задание из списка задач.

Что я думал, когда писал этот код? честно не помню. Наверное, ни о чем не думает. Это основная проблема многих ошибок.

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

Что происходит?

Представьте мое удивление, когда я начал тестировать NotesManager. Я обнаружил, что, когда я обозначил некоторые задачи как «выполненные», они не были удалены из списка задач. Казалось, что это было совершенно случайно, иногда работал, а иногда нет.

Вот я и недоверчиво смотрел на отладчик. Задание сидит именно здесь в списке задач, но «удалить» не удаляло его. Я понятия не имел, что происходит.

Я предположил, что с реализацией NoteComparer что-то неверно. Я добавил точку остановки в методе Compare. Там я обнаружил что-то странное: задачи не сканировались последовательно. Казалось, что отладчик случайно обращался к элементам в списке задач.

Хммм Удивительно. На секунду я подумал, что может происходить какая-то странная многопоточность, но это была локальная среда разработки — никто другой не мог бы получить доступ к моему веб-серверу (и если и был, насколько вероятно, они тестируют того же пользователя и данные, которые я сейчас использовал?). Нет, ответ должен быть где-то в другом месте.

После еще нескольких тестов обнаружилась закономерность. Первый доступ к Compare был где-то в центре списка. Затем он перескочил в другое место. Затем еще один скачок и еще один, прежде чем окончательно отказаться от всего. Затем пришел момент #facepalm, и я понял, что SortedList должен использовать двоичный поиск для поиска элементов в списке! Это должно было быть очевидным (все остальное было бы бессмысленным, на самом деле).

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

На этот раз я переместил остановку точку чуть ниже в реализации Comparer. Я сразу увидел, где проблема. Я передавал NoteIndex только с идентификатором, предполагая, что этого достаточно для равенства.

Будь это обычный список, это бы сработало. Но отрезание этого угла в сочетании с двоичным поиском (вместо последовательного сканирования, которое я неявно предполагал) привело к тому, что SortedList не смог найти нужное примечание. Поэтому я изменил реализацию MarkDone.

И это сработало!

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

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

Ключевые вещи на вынос

Вот мои ключевые выводы из этого дела:

  1. Если вы используете новую службу или структуру данных, уделите 5 минут для прочтения документации. Если бы я сделал это и понял, что ключ в SortedList использовался для уникальности, а не только для сортировки, я бы, вероятно, не совершил ошибки.
  2. Для повседневной работы нужно отлично владеть основными структурами данных и методами. Этот тип ошибок очень трудно найти и устранить. Это происходит спорадически без видимой логики. Лучше вообще избегать такого типа ошибок, но если вы не можете избежать этого, по крайней мере, сможете проанализировать его после того, как это произойдет.

Бонусный вопрос

Почему я переопределил GetHashCode() в классе Note? Почему вы должны? всегда заменить GetHashCode(), если вы переопределили Equals()?

Подсказка: какая структура данных использует хэш-коды?

Нравится то, что вы читали? Поделитесь любовью, хлопая. Есть вопросы или комментарий? Дайте мне знать в разделе комментариев.

Добавить комментарий

Ваш адрес email не будет опубликован.