2

我在 Java 中复制了一个 C# 类。（我是 Java 新手。）

我的班级需要跟踪与双精度相关的 int 值。然后，只要一个值低于或高于双打，它就需要创建一个 Alerter(int) 。

Alerter.LatencySensitiveAction() ，需要立即调用，它是延迟敏感和时间关键的代码。DoubleMap 类的目的是尽可能快地调用 LatencySensitiveAction()。

DoubleMap.OnData() 是该类的延迟敏感方法（如下）。

TreeMap 有意义吗？我在 C# 中使用 SortedList。我正在寻找一个关联集合，该集合以快速遍历的排序顺序存储键/值对。

有人告诉我这个 Java 代码

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

效率不高，因为它创建了一个新对象。我应该改用什么？

所以基本上，我在问使用哪个集合可以将 double 与 int 相关联，以排序顺序存储，以及按顺序遍历集合的最快方法是什么。

我相信我的 C# 代码（如下）可以完成这项工作，需要帮​​助将其转换为 Java。如果您认为我的 C# 代码也可以改进.. 请告诉.. ty。

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);
    }
}
4

3 回答 3

3

如果延迟对您来说如此重要，我建议您实现一个自定义类来处理您的订单簿（这是一个订单簿，对吗？:-)）

我建议如下：

  • 代表价格的双精度数组（ps 为什么要使用双精度？这不应该是 BigDecimal 还是定点整数以避免浮点不准确？）
  • 订单大小的相应 long 数组
  • 相应的警报器数组
  • 根据价格对所有数组进行排序
  • 然后，您可以直接在价格数组上使用二进制搜索来查找任何给定范围内的价格

这种方法将为您提供非常低的延迟。

缺点是添加/删除订单是 O(n)。但它是如此便宜的 O(n) 只有三个arraycopys，除非您的订单非常大，否则开销将非常低，以至于您不会注意到。

您可能还对包含一组非常低延迟的 Java 库的Javolution感兴趣，我认为其中一些是专门为交易应用程序设计的。

于 2012-03-05T02:34:30.723 回答
0

如果你只是做遍历，你为什么要使用地图呢？您不能在小于 O(n) 的时间内执行遍历。

我建议您制作一个对象来封装订单，并查看 PriorityQueue 以获取您的收藏。

如果您需要进行范围搜索，您还可以查看 TreeSet（如果您的值是唯一的）或 TreeMap。（但请注意，您必须以某种方式进行迭代才能从这些类中获得排序输出。）

编辑

您确定您的审阅者的意思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()性能。

于 2012-03-05T02:33:06.917 回答
0

在现代操作系统上处理“低延迟”应用程序时要记住的一件事是它是抢占式的。它不是实时操作系统，因此任何线程都可以随时挂起，并且不保证响应时间。如果您正在尝试实现真正的低延迟/一致的延迟，那么至少您需要在任务调度程序中将您的应用程序推送到实时。虽然即使这也不是真正的实时，但它会帮助您的线程获得更多的处理器时间。还要考虑GC可以停止线程清理。

如果您真的对实现最低延迟或至少更有保证的延迟感兴趣，那么我至少会切换到 C++ 或 C。至少那时您可以控制内存分配而不必担心 GC 会发生在您下方并导致意外延迟。

于 2012-03-05T04:45:30.317 回答