Latched, pinned, and marked dirty

> три индирекшена получается

ох-ох. а что делать? задача такая: есть несортированный List[20000] of класс (или struct) со свойством double Rank, надо из него как можно быстрее взять top 10 (или next top 10, но реже), или next next top 10, но ещё реже.

From:

ну я пока охочусь на low hanging fruits. как их все подберу, если ещё надо будет, то буду профилировать, конечно.

From:

Partial sort?

From:

что это такое?

From:

Алгоритм, который выдает отсортированными top k элементов массива. http://en.wikipedia.org/wiki/Partial_sorting

From:

эээ... это то, что я написал :)
но мне нужен код, а ни List, ни Linq не умеют partial sort.

From:

al-zatv.livejournal.com

а тебе нужны точные 10 лучших, или так-сяк-примерно? вот такая супербыстрая штукень http://ru.wikipedia.org/wiki/Корзинная_сортировка , если надо примерно лучшие определить,работает за линейное время.

From:

wizzard

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

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

причем инлайнера нынешнего даже хватает, можно написать на генериках список с втыкающимся компаратором без оверхеда

но, увы, дефолтный лист этого не делает.

From:

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

From:

ну если что-то писать вручную, то не полную сортировку, а partial sort, как мне подсказывают. но удивило, что я не нашёл C# имплементации в сети вообще. может, он не настолько быстрее (или совсем не быстрее)?

From:

Наверняка ведь в ранке не нужна точность до 52 бита после запятой?

1. Формируем список даблов из ранков, попутно округляя значения до 20 бита после запятой и запихивая в младшие биты индекс того элемента в исходном списке, из которого взяли ранк.
2. Сортируем полученный список даблов.
3. Из младших битов первых десяти элементов отсортированного списка выковыриваем индексы Top10 элементов исходного списка.
4. Профит.

From:

отлично! завтра проверю, насколько быстро можно запихнуть индекс в double. через BitConverter, или есть более быстрый вариант?

From:

vsi.livejournal.com

я тоже хотел предложить нечто вроде, только вместо бит конвертора умножить целую часть на 100000 и прибавить индекс. только вот не понятно насколько оно вообще нужно, у меня в тесте на коленке и обычный OrderBy неплохо работает, медленнее конечно чем list.sort но не в 10 раз

var rnd = new Random();
var items = Enumerable.Range(0, 10000).Select(i => new { DoubleValue = rnd.NextDouble() * 1000000d }).ToArray();

for (int q = 0; q < 3; q++)
{
// a
var rank = items.Select((i, idx) => { var d = i.DoubleValue; var f = Math.Floor(d); return f * 100000 + idx + d - f; }).ToList();

// b
rank.Sort();

// c
var sorted = items.OrderBy(i => i.DoubleValue).ToArray();
}

#0
a: 4.4031 ms
b: 1.0667 ms
c: 6.1935 ms

#1
a: 0.8753 ms
b: 1.1806 ms
c: 4.4381 ms

#2
a: 0.8472 ms
b: 1.0270 ms
c: 4.3769 ms

From:

тест, который я здесь вижу, меряет скорость List[double].Sort, не так ли? для моих целей, это достаточно быстро. что недостаточно быстро, так это скорость List[MyClass]. поскольку Linq ещё медленнее, то what's your point, exactly?

From:

vsi.livejournal.com

поинт в том, что, возможно, не нужно сортировать "List[MyClass] с компарером по тому же double", а вместо этого сортировать ienumarable

[Error: Irreparable invalid markup ('<struct/object>') in entry. Owner must fix manually. Raw contents below.]

поинт в том, что, возможно, не нужно сортировать "List[MyClass] с компарером по тому же double", а вместо этого сортировать ienumarable<struct/object>.OrderBy-ем, который медленнее чем list<double>.sort всего в 3.5 раза, а не в 10 как List[MyClass] с компарером. если конечно то не была просто фигура речи. orderby, конечно, будет потреблять больше памяти

From:

vsi.livejournal.com

мда, естествоиспытатель из меня не очень. когда скомпилить все в release и запустить не из под дебагера, то OrderBy оказывается в 2 раза тормознее list[t].sort(comparer[t]), а sort(comparer), в свою очередь, в 4-6 раз тормознее чем list[double].sort()

From:

Я сделал по-простому, через масштабирование и округление до целого.

C:\xxx\fastsort>cat fastsort.cs
using System;
using System.Diagnostics;
using System.Linq;
using System.Collections.Generic;

public class Program
{
    public const int ListSize = 10000;
    public const int NRuns = 1000;

    public const int precision = 1 << 23;  // Keep single-float's 23 bits of significance

    private static Random Rng = new Random();

    struct WrappedDouble : IComparable<WrappedDouble>
    {
        public WrappedDouble(double value) : this() { Value = value; }
        public double Value;
        public int CompareTo(WrappedDouble o) { return Value.CompareTo(o.Value); }
    }

    public static void Main()
    {
        SortList(() => (float)Rng.NextDouble());
        SortList(() => Rng.NextDouble());
        SortList(() => new WrappedDouble(Rng.NextDouble()));
        SortStructListFast();
    }

    public static void SortList<T>(Func<T> funGenerateElement)
    {
        List<T>[] lists = GenerateManyLists(NRuns, ListSize, funGenerateElement);

        Stopwatch sw = Stopwatch.StartNew();

        for (int i = 0; i < lists.Length; ++i)
            lists[i].Sort();

        Console.WriteLine("Sorting {0}: {1}ms", typeof(T), sw.ElapsedMilliseconds);
    }

    public static void SortStructListFast()
    {
        List<WrappedDouble>[] lists = GenerateManyLists(NRuns, ListSize, () => new WrappedDouble(Rng.NextDouble()));

        Stopwatch sw = Stopwatch.StartNew();

        for (int i = 0; i < lists.Length; ++i)
        {
            // Unrolling elegant Select into ugly for-loop: 40% speedup
            // List<double> tmp_collection_for_sorting = lists[i].Select((e, j) => (Math.Round(e.Value * precision) + (double)j / precision) / precision).ToList();

            List<double> tmp_collection_for_sorting = new List<double>(lists[i].Count);
            for (int j = 0; j < lists[i].Count; ++j)
                tmp_collection_for_sorting.Add((Math.Round(lists[i][j].Value * precision) + (double)j / precision) / precision);

            tmp_collection_for_sorting.Sort();

            WrappedDouble[] top10 = tmp_collection_for_sorting.Take(10).Select(e => lists[i][(int)((e * precision - Math.Round(e * precision)) * precision)]).ToArray();

            // Validation must be commented out for profiling runs
            // var expected_top10 = lists[i].OrderBy(e => e.Value).Take(10);
            // if (!top10.SequenceEqual(expected_top10))
            // {
            //    expected_top10.Zip(top10, (e, a) => new { Expected = e.Value, Actual = a.Value }).Dump();
            //    throw new Exception("BANG!");
            // }
        }

        Console.WriteLine("Sorting structs fast: {0}ms", sw.ElapsedMilliseconds);
    }

    private static List<T>[] GenerateManyLists<T>(int nLists, int listSize, Func<T> funGenerateElement)
    {
        return Enumerable.Range(0, nLists).Select(_ => Enumerable.Range(0, listSize).Select(__ => funGenerateElement()).ToList()).ToArray();
    }
}

C:\xxx\fastsort>csc fastsort.cs
Microsoft (R) Visual C# Compiler version 4.0.30319.33440
for Microsoft (R) .NET Framework 4.5
Copyright (C) Microsoft Corporation. All rights reserved.

C:\xxx\fastsort>fastsort.exe
Sorting System.Single: 705ms
Sorting System.Double: 651ms
Sorting Program+WrappedDouble: 1506ms
Sorting structs fast: 834ms

Edited Date: 2014-01-10 12:03 am (UTC)

From:

С BitConverter подход более хакерский, но получается ещё быстрее:

    public const int precision = 1 << 23;  // [For rounding approach] Keep single-float's 23 bits of significance
    public const ulong Mask = 0xFFFFF;     // [For direct bit-hacking approach] Abuse 20 least-significant bits

    ...

    public static void SortStructListBitHacking()
    {
        List<WrappedDouble>[] lists = GenerateManyLists(NRuns, ListSize, () => new WrappedDouble(Rng.NextDouble()));

        Stopwatch sw = Stopwatch.StartNew();

        for (int i = 0; i < lists.Length; ++i)
        {
            List<double> tmp_collection_for_sorting = new List<double>(lists[i].Count);
            for (uint j = 0; j < lists[i].Count; ++j)
            {
                tmp_collection_for_sorting.Add(
                    (BitConverter.Int64BitsToDouble(
                        (long)(((ulong)BitConverter.DoubleToInt64Bits(lists[i][(int)j].Value) & ~Mask) + j))));
            }

            tmp_collection_for_sorting.Sort();

            WrappedDouble[] top10 = tmp_collection_for_sorting.Take(10).Select(e => lists[i][(int)((ulong)BitConverter.DoubleToInt64Bits(e) & Mask)]).ToArray();
        }

        Console.WriteLine("Sorting via bit hacking: {0}ms", sw.ElapsedMilliseconds);
    }

C:\xxx\fastsort>fastsort.exe
Sorting System.Single: 751ms
Sorting System.Double: 708ms
Sorting Program+WrappedDouble: 1612ms
Sorting via rounding: 893ms
Sorting via bit hacking: 783ms

From:

Должно быть быстрее. Фактически, O(n). Алгоритм простой, так что должно быть несложно попробовать и сравнить.

From:

Мои пять копеек:

    private static void PartialSort()
    {
        List[] lists = GenerateManyLists(NRuns, ListSize, () => new WrappedDouble(Rng.NextDouble()));
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < lists.Length; ++i)
        {
            PartialQuickSort(lists[i], 0, lists[i].Count - 1, 10);
            //var top10 = lists[i].Take(10).ToList();
            //var expected_top10 = lists[i].OrderByDescending(e => e.Value).Take(10).ToList();
            //if (!top10.SequenceEqual(expected_top10))
            //{
            //    for (int j = 0; j < 10; ++j)
            //    {
            //        Console.WriteLine("actual {0} expected {1}", top10[i].Value, expected_top10[i].Value);
            //    }
            //    throw new Exception("BANG!");
            //}
        }
        Console.WriteLine("Sorting structs with partial quicksort: {0}ms", sw.ElapsedMilliseconds);
    }

    private static void PartialQuickSort(List list, int left, int right, int cnt)
    {
        if (left < right)
        {
            int pivotIdx = Partition(list, left, right);
            PartialQuickSort(list, left, pivotIdx - 1, cnt);
            if (left + cnt > pivotIdx)
                PartialQuickSort(list, pivotIdx + 1, right, left + cnt - pivotIdx);
        }
    }

    private static void Swap(List list, int index1, int index2)
    {
        T t = list[index1];
        list[index1] = list[index2];
        list[index2] = t;
    }

    private static int Partition(List list, int left, int right) where T : IComparable
    {
        int i = left, j = right;
        while (i < j)
        {
            if (list[i].CompareTo(list[left]) < 0)
            {
                Swap(list, i, j);
                --j;
            }
            else
                ++i;
        }
        if (list[i].CompareTo(list[left]) < 0)
            i--;
        Swap(list, left, i);
        return i;
    }

Результаты (в сравнении с остальными твоими алгоритмами):

Sorting System.Single: 760ms
Sorting System.Double: 741ms
Sorting Program+WrappedDouble: 1655ms
Sorting structs fast: 951ms
Sorting via bit hacking: 938ms
Sorting structs with partial quicksort: 615ms

From:

У меня на машине эффект ещё драматичнее:

Sorting System.Single: 708ms
Sorting System.Double: 659ms
Sorting Program+WrappedDouble: 1515ms
Sorting via rounding: 853ms
Sorting via bit hacking: 731ms
Sorting structs with partial quicksort: 338ms

Неожиданно. Спасибо, что не поленился написать. Хорошая иллюстрация к "all we need to remember is that intuition is an ineffective approach to writing efficient code." (c) Alexandrescu

From:

спасибо!

From:

wow! спасибо!

From:

al-zatv.livejournal.com

Функция получения номера корзины (Макс-мин)/ЧислоКорзин. Дофига элементов свалиться в одну корзину могут. Но, для многих задач, если элементы близки,то и примерно пофиг в каком порядке их брать, так что можно брать любые 10 из первой корзины,и все будет ок. Зависит от задачи,конечно.

From: