Преобразование класса, чувствительного к задержке C # в Java, будет ли TreeMap заменять SortedList в моем случае? - PullRequest
Новая
       0

Преобразование класса, чувствительного к задержке C # в Java, будет ли TreeMap заменять SortedList в моем случае?

2 голосов
/ 05 марта 2012

Я реплицирую класс C # на Java. (Я новичок в Java.)

Мой класс должен отслеживать значения типа int, связанные с double. Затем он должен создать Alerter (int) всякий раз, когда значение пересекается ниже или выше двойных.

Alerter.LatencySensitiveAction (), должен вызываться немедленно, он чувствителен к задержке и критичен по времени. Цель класса DoubleMap - вызвать LatencySensitiveAction () как можно быстрее.

DoubleMap.OnData () - чувствительный к задержке метод класса (ниже).

Имеет ли смысл TreeMap? Я использую SortedList в C #. Я ищу ассоциативную коллекцию, которая хранит пары ключ / значение в отсортированном порядке с быстрым обходом.

Мне сказали, что этот код Java 

for (Map.Entry<Double,Alerter> entry : mAscend.entrySet() )

неэффективен, потому что он создает новый объект. Что я должен использовать вместо этого?

Итак, в основном, я спрашиваю, какую коллекцию использовать, которая может ассоциировать double и int, хранится в отсортированном порядке, и какой самый быстрый способ пройти по коллекции в порядке.

Я полагаю, что мой код C # (ниже) делает свою работу, и мне нужна помощь с его преобразованием в Java. Если вы думаете, что мой код C # тоже можно улучшить .. пожалуйста, скажите .. ты.

Java-код: 

public class DoubleMap {

    TreeMap<Double,Alerter> mAscend, mDecend, mHoldAscend, mHoldDecend;

    public DoubleMap()
    {
        mAscend = new TreeMap<Double, Alerter>();
        mDecend = new TreeMap<Double, Alerter>(new ReverseComparator());
    }

    public void Add(boolean rAscend, double value, int size)
    {
        TreeMap<Double,TradeOrder> list = rAscend ? mAscend : mDecend;

        Alerter to = list.get(value);
        if ( to != null )
        {
            Alerter.size += size;
        }
        else 
        {
            to = new Alerter (size);           
            list.put(value, to);
        }
    }

    public void Remove(boolean rAscend, double value, int size)
    {
        TreeMap<Double,TradeOrder> list = rAscend ? mAscend : mDecend;

        Alerter to = list.get(value);
        if ( to != null )
        {
            long nsize = to.size - size;
            if ( nsize <= 0 )
                list.remove(value);
            else
                to.size = nsize;
        }
    }

    public void Ondata(double rValue)
    {
        for (Map.Entry<Double,Alerter> entry : mAscend.entrySet() )
        {
            if ( entry.getKey() > rValue )
                break;

            entry.getValue().LatencySensitiveAction();

            if ( mHoldAscend == null )
                mHoldAscend = new TreeMap<Double,Alerter>(mHoldAscend);
            mAscend.remove(entry.getKey());
        }

        for (Map.Entry<Double,TradeOrder> entry : mDecend.entrySet() )
        {
            if ( entry.getKey() < rValue )
                break;

            entry.getValue().LatencySensitiveAction();

            if ( mHoldDecend == null )
                mHoldDecend = new TreeMap<Double,TradeOrder>(mHoldDecend);
            mHoldDecend.remove(entry.getKey());
        }

        if ( mHoldAscend != null )
        {
            mAscend = mHoldAscend;
            mHoldAscend = null;
        }

        if ( mHoldDecend != null )
        {
            mDecend = mHoldDecend;
            mHoldDecend = null;
        }

    }
}

C # код: 

public class DoubleMap
{
    private SortedList<double, Alerter> mAscend, mDecend, mHoldAscend, mHoldDecend;

    public DoubleMap()
    {
        mAscend = new SortedList<double, Alerter>();
        mDecend = new SortedList<double, Alerter>(new DescendingComparer<double>());
    }

    public void Add(bool rAscend, double rValue, long rSize)
    {
        var list = rAscend ? mAscend : mDecend;
        Alerter to;
        if (list.TryGetValue(rValue, out to))
        {
            to.Size += rSize;
        }
        else
        {
            to = new Alerter(rSize);
            list.Add(rValue, to);
        }
    }

    public void Remove(bool rAscend, double rValue, long rSize)
    {
        var list = rAscend ? mAscend : mDecend;
        Alerter to;
        if (list.TryGetValue(rValue, out to))
        {
            long nqty = to.Size - rSize;
            if (nqty <= 0)
            {
                list.Remove(rValue);
            }
            else
                to.Size = nqty;
        }
    }

    public void OnData(double rValue)
    {
        foreach (var pair in mAscend)
        {
            if (pair.Key > rValue)
                break;

            pair.Value.LatencySensitiveAction();

            if (mHoldAscend == null)
                mHoldAscend = new SortedList<double, Alerter>(mAscend);
            mHoldAscend.Remove(pair.Key);
        }

        foreach (var pair in mDecend)
        {
            if (pair.Key < rValue)
                break;

            pair.Value.LatencySensitiveAction();

            if (mHoldDecend == null)
                mHoldDecend = new SortedList<double, Alerter>(mDecend, new DescendingComparer<double>());
            mHoldDecend.Remove(pair.Key);
        }

        if (mHoldAscend != null)
        {
            mAscend = mHoldAscend;
            mHoldAscend = null;
        }

        if (mHoldDecend != null)
        {
            mDecend = mHoldDecend;
            mHoldDecend = null;
        }
    }
}

class DescendingComparer<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        return y.CompareTo(x);
    }
}

Ответы [ 3 ]

3 голосов
/ 05 марта 2012

Если задержка так важна для вас, я бы порекомендовал реализовать собственный класс для обработки вашей книги заказов (это книга заказов, верно? :-))

Я бы предложил что-то вроде следующего:

  • Массив значений типа double, представляющих цены (p.s. почему вы используете double? Разве это не должно быть либо BigDecimal, либо целым числом с фиксированной точкой, чтобы избежать неточностей с плавающей запятой?)
  • Соответствующий массив длин для размеров заказа
  • Соответствующий массив оповещателей
  • Сортировка всех массивов по цене
  • Затем вы можете использовать двоичный поиск непосредственно в массиве цен для поиска цен в любом заданном диапазоне

Этот подход даст вам очень низкую задержку.

Недостатком является то, что это O (n) для добавления / удаления ордеров. Но это такой дешевый O (n) всего с тремя arraycopy s, что, если ваша книга заказов не очень большая, накладные расходы будут настолько низкими, что вы не заметите.

Возможно, вас также заинтересует Javolution , который содержит набор библиотек с очень низкой задержкой для Java, я думаю, некоторые из них специально предназначены для торговых приложений.

0 голосов
/ 05 марта 2012

При работе с приложениями с «малой задержкой» в современной ОС следует помнить, что она имеет преимущественную силу. Это не операционная система реального времени, поэтому любой поток может быть приостановлен в любое время, и нет никаких гарантий относительно времени отклика. Если вы пытаетесь добиться честной низкой задержки / постоянной задержки, то, по крайней мере, вам нужно будет отправить свои приложения в реальном времени в планировщике задач. Хотя даже это не соответствует действительности в реальном времени, но это поможет вашим потокам получить больше процессорного времени. Также учтите, что сборщик мусора может остановить очистку потоков.

Если вы действительно заинтересованы в достижении минимальной задержки или, по крайней мере, более гарантированной задержки, то я бы по крайней мере переключился на C ++ или C. По крайней мере, тогда вы можете контролировать выделение памяти и не беспокоиться о GC идет под вами и вызывает неожиданную задержку.

0 голосов
/ 05 марта 2012

Если вы делаете только обход, зачем вообще использовать карту? Вы не можете выполнить обход менее чем за O (n).

Я бы порекомендовал вам создать объект для инкапсуляции заказа и взглянуть на PriorityQueue для вашей коллекции.

Если вам нужно выполнить поиск по диапазону, вы также можете посмотреть TreeSet (если ваши значения уникальны) или TreeMap. (Но учтите, что вам нужно выполнить итерацию определенным способом, чтобы получить отсортированный вывод из этих классов.)

EDIT

Вы уверены, что ваш рецензент имел в виду, что for (Map.Entry<Double,Alerter> entry : mAscend.entrySet()) был неэффективным, а не код внутри цикла for? Вы выполняете создание новой коллекции каждый раз, когда подходите к паре (сама по себе недешевая работа и, конечно, не очень хорошая вещь для кода, чувствительного ко времени). Вы делаете то же самое в вашем коде C #.

Попробуйте это: 

Code Deleted; See history

РЕДАКТИРОВАТЬ 2

Я понял, что ваша реализация на самом деле намного медленнее, чем необходимо, потому что она полагается исключительно на TreeMap для выполнения как сортировки, так и поиска. Вот намного более быстрая реализация: 

public class DoubleMap {
    HashMap<Double, Alerter> mAscend, mDescend;
    PriorityQueue<Double> pricesAscending, pricesDescending;

    public DoubleMap()
    {
        pricesAscending = new PriorityQueue<Double>(100);
        pricesDescending = new PriorityQueue<Double>(100, new ReverseComparator());
    }

    public void Add(boolean rAscend, double value, int size)
    {
        Map<Double, Alerter> map = rAscend ? mAscend : mDescend;

        Alerter to = map.get(value);
        if ( to != null )
        {
            Alerter.size += size;
        }
        else 
        {
            to = new Alerter (size);           
            map.put(value, to);
            pricesAscending.offer(value);
            pricesDescending.offer(value);
        }
    }

    public void Remove(boolean rAscend, double value, int size)
    {
        Map<Double, Alerter> map = rAscend ? mAscend : mDecend;

        Alerter to = map.get(value);
        if ( to != null )
        {
            long nsize = to.size - size;
            if ( nsize <= 0 )
                map.remove(value);
                pricesAscending.remove(value);
                pricesDescending.remove(value);
            else
                to.size = nsize;
        }
    }

    public void Ondata(double rValue)
    {
        while (pricesAscending.peek() < rValue) {
            mAscend.getValue(pricesAscending.peek()).LatencySensitiveAction();

            mAscend.remove(pricesAscending.poll());
        }

        while (pricesDescending.peek() > rValue) {
            mDescend.getValue(pricesDescending.peek()).LatencySensitiveAction();

            mDescend.remove(pricesDescending.poll());
        }
    }
}

Отличия: HashMap имеет операции get() и remove() постоянного времени, где TreeMap имеет производительность O(log(n)) для этих операций.

PriorityQueue имеет постоянную производительность peek() и poll().

...