0

我想将整数保存在数据结构中，但不知道我可能得到的整数数量。我希望数据库是 FIFO 类型的。什么最适合这个目的？

4

5 回答 5

7

除了使用数据库之外，如果您只有许多整数，您可以将它们写入普通文件。普通文件保留顺序，但删除条目可能会很昂贵。

您可以使用普通文件在大约 0.1 秒内写入/重写 100 万个整数。

一个有效的 int 基元集合是 TIntArrayList。它就像@JPelletier 的建议，但包装了一个 int[]。一百万个 int 值应该占用大约 4 MB 的内存或磁盘。

编辑：这表明对于 100 万个数字，ArrayList 是一个糟糕的选择。主要是因为 remove(0) 是 O(n) 而不是 O(1)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

// based on http://www.cs.princeton.edu/introcs/43stack/RingBuffer.java.html
public class IntRingBuffer {
    private final int[] a;       // queue elements
    private int N = 0;           // number of elements on queue
    private int first = 0;       // index of first element of queue
    private int last  = 0;       // index of next available slot

    // cast needed since no generic array creation in Java
    public IntRingBuffer(int capacity) {
        a = new int[capacity];
    }

    public boolean isEmpty() { return N == 0; }
    public int size()        { return N;      }

    public void enqueue(int item) {
        if (N == a.length) { throw new RuntimeException("Ring buffer overflow"); }
        a[last] = item;
        last = (last + 1) % a.length;     // wrap-around
        N++;
    }

    // remove the least recently added item - doesn't check for underflow
    public int dequeue() {
        if (isEmpty()) { throw new RuntimeException("Ring buffer underflow"); }
        int item = a[first];
        N--;
        first = (first + 1) % a.length;   // wrap-around
        return item;
    }

    public static void main(String... args) {
        int size = 1000000;
        {
        long start = System.nanoTime();
        IntRingBuffer list = new IntRingBuffer(size);
        for(int i=0;i< size;i++)
            list.enqueue(i);
        for(int i=0;i< size;i++)
            list.dequeue();
        long time = System.nanoTime() - start;
        System.out.println(list.getClass().getSimpleName()+": Took "+time/1000/1000+" ms to add/remove "+size+" elements");
        }
        {
        long start = System.nanoTime();
        List<Integer> list = new LinkedList<Integer>();
        for(int i=0;i< size;i++)
            list.add(i);
        for(int i=0;i< size;i++)
            list.remove(0);
        long time = System.nanoTime() - start;
        System.out.println(list.getClass().getSimpleName()+": Took "+time/1000/1000+" ms to add/remove "+size+" elements");
        }
        {
        long start = System.nanoTime();
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i< size;i++)
            list.add(i);
        for(int i=0;i< size;i++)
            list.remove(0);
        long time = System.nanoTime() - start;
        System.out.println(list.getClass().getSimpleName()+": Took "+time/1000/1000+" ms to add/remove "+size+" elements");
        }

    }
}

印刷

IntRingBuffer: Took 31 ms to add/remove 1000000 elements
LinkedList: Took 252 ms to add/remove 1000000 elements
ArrayList: Took 325832 ms to add/remove 1000000 elements
于 2011-01-18T13:57:40.897 回答
1

您可以使用 JDBC 访问的任何关系数据库：MySQL、PostgreSQL、Oracle、SQLServer、DB2、Informix、Interbase、Firebird、Ingress，应有尽有。

如果你正在寻找轻量级的东西，你可以看看SQLite's API for Java。

于 2011-01-18T13:49:35.333 回答
1

我不认为真的有“FIFO 数据库”这样的东西。数据库通常允许您使用某种索引方案以任何所需的顺序访问数据。您可以通过将序列号附加到每条记录并按顺序读取它们来在数据库中实现 FIFO 队列。我曾经使用过的任何数据库都可以做到这一点。

也许简单的答案就是 Pablo 给出的答案：使用任何关系数据库。选择 MySQL 或 Postgres 之类的免费工具之一，使用它并了解它们的用途。

于 2011-01-18T13:56:25.223 回答
1

你真的是指数据库吗？因为您可以为此使用ArrayList：

ArrayList<Integer> array = new ArrayList<Integer>();
array.add(3);
array.add(4);
array.add(5); // Appends to the end of this list

int myInt = array.remove(0); // Return first element

如果你真的需要一个数据库，你能告诉我们你想要做什么的更多细节吗？

[编辑] 我建议您阅读：Java 最佳实践 – Vector vs ArrayList vs HashSet谢谢！

于 2011-01-18T13:59:20.700 回答
0

听起来你在谈论队列。查看 JMS，看看这是否是您正在寻找的概念。虽然对于这样一个简单的任务，它看起来像是一个大工具，但它会为您提供 FIFO 的持久化（到您希望的任何数据库）功能。

于 2011-01-18T14:02:25.473 回答