четверг, 2 октября 2014 г.

Сортировка случайных строк по одной из их частей.

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

Подводный камень номер один - производительность. Если использовать для выделения первой части строки string.Split(), то производительность падает пропорционально длине строк, раз, и размеру текста - два.  Эту проблему можно решить, используя регулярные выражения.
Например, для строк нашего типа можно сделать вот так:

 
    string line = "1 тест";
    string firstNumber = Regex.Match(line, "^(.*?)\s.*$").Groups[1].Value;

Подробно о результатах сравнения производительности .Split() и Regex я напишу в отдельном посте, а сейчас продолжим. Итак, мы получили первый элемент строки, по которому нам нужно сортировать, теперь нужно придумать как сортировать строки.



На самом деле, если подумать, то решение очевидно - нам нужен объект, который будет хранить и часть строки в номером, и саму строку. Напрашивается HashTable, но его, к сожалению, нельзя сортировать. Самый эффективный вариант - использовать любую коллекцию, элементом которой будет объект содержащий необходимые нам данные. В данном случае нас вполне устроит банальный Tuple<string, string> в качестве объекта данных и, соответственно List<Tuple<string, string>> в качестве списка объектов.

После того, как мы пройдем все пришедшие и добавим их в List, все, что нам остается сделать, это вот так:

 
   stringlist.Sort((x, y) =>x.Item1.CompareTo(y.Item1));
   stringlist.Select(x=>x.Item2);

Вуаля! В result мы получили список строк отсортированный по первому элементу.

Комментариев нет:

Отправить комментарий