Pull to refresh
3
Karma
0
Rating

Алгоритмическая сложность итерирования по хэшсету в C#

Lumber room
Исследуя Reflector'ом внутренности классов .NET фреймворка, нередко можно узнать много любопытных вещей. Например, однажды (довольно давно) я узнал, что для дотнетовского QuickSort можно очень просто придумать такой класс входных данных, на которых сортировка будет осуществляться за квадратичное время. Так, на массивах-«пирамидках» (то есть на таких, в которых максимальный элемент находится посередине, второй и третий по величине — слева и справа от него, и так далее) быстрая сортировка была сравнима по времени с пузырьковой. Причина очевидна — в качестве медианы выбирался средний элемент массива. Как с этой проблемой дело обстоит сейчас, не знаю, но если она всё ещё имеет место — это заслуживает отдельного поста.

Речь сейчас пойдёт о другом. Всем, кто знаком с дотнетом, полагаю, известен класс System.Collections.Generic.HashSet<T>. Как гласит MSDN, класс HashSet предоставляет высокопроизводительные операции над множествами. Как вы думаете, за какое время ваш компьютер, скажем, двести раз пробежит по хэшсету из одного элемента? Сотая доля секунды? Меньше? Вовсе не факт!
Об этом - дальше.
Total votes 22: ↑14 and ↓8 +6
Views1.6K
Comments 12

News

Show more

5 cпособов осуществить агрегацию строк в MS SQL

Lumber room
Иногда возникает необходимость осуществить агрегацию строк в SQL запросе, то есть, по такому набору данных:
GroupId Item
1 AAA
2 IS
5 OMG
2 WHAT
2 THE
1 This
получить примерно такой:
GroupId ItemList
1 AAA,This
2 IS,WHAT,THE
5 OMG
MySQL, например, для таких целей обладает встроенной функцией GROUP_CONCAT():
SELECT GroupId, GROUP_CONCAT(Item SEPARATOR ",") AS ItemList
FROM Items

В MS SQL Server'e такой функции нету, поэтому приходится извращаться. Перед тем, как приступить, сделаем скрипт для создания тестовой таблицы:
CREATE TABLE Items(GroupId INT, Item NVARCHAR(10))

INSERT INTO Items(GroupId, Item)
SELECT 1 AS GroupId, 'AAA' AS Item
  UNION ALL
SELECT 2, 'IS'
  UNION ALL
SELECT 5, 'OMG'
  UNION ALL
SELECT 2, 'WHAT'
  UNION ALL
SELECT 2, 'THE'
  UNION ALL
SELECT 1, 'This'

Итак, начнем.
Читать дальше →
Total votes 15: ↑9 and ↓6 +3
Views7.3K
Comments 9

Information

Rating
5,787-th
Registered
Activity