标签: data-structures

我知道地图是一种将键映射到值的数据结构.字典不一样吗？地图和字典^1有什么区别？

_{1.我不是在询问它们是如何在X或Y语言中定义的(这似乎是人们通常在这里提出的问题),我想知道它们在理论上的区别.}

请不要说EHCache或OSCache等.为了这个问题的目的,假设我只想使用SDK(从实践中学习)来实现我自己的.鉴于缓存将在多线程环境中使用,您将使用哪些数据结构？我已经使用LinkedHashMap和Collections#synchronizedMap实现了一个,但我很好奇任何新的并发集合是否会更好.

更新:当我发现这个金块时,我只是阅读Yegge的最新消息:

如果您需要持续时间访问并希望维护插入顺序,那么您不能比LinkedHashMap做得更好,这是一个真正精彩的数据结构.它可能更精彩的唯一方法是如果有并发版本.可惜.

在我使用上面提到的LinkedHashMap+ Collections#synchronizedMap实现之前,我的想法几乎完全相同.很高兴知道我不只是忽略了一些东西.

基于到目前为止的答案,对于高度并发的LRU来说,我最好的选择是使用一些相同的逻辑来扩展ConcurrentHashMapLinkedHashMap.

在C中,我知道我可以使用以下代码在堆上动态分配二维数组:

int** someNumbers = malloc(arrayRows*sizeof(int*));

for (i = 0; i < arrayRows; i++) {
    someNumbers[i] = malloc(arrayColumns*sizeof(int));
}

显然,这实际上会创建一个指向一堆独立的一维整数数组的指针的一维数组,而"系统"可以在我要求时找出我的意思:

someNumbers[4][2];

但是,当我静态声明一个2D数组时,如下一行...:

int someNumbers[ARRAY_ROWS][ARRAY_COLUMNS];

...是否在堆栈上创建了类似的结构,还是完全是另一种形式？(即它是指针的一维数组吗？如果没有,它是什么,以及如何计算它的引用？)

另外,当我说"系统"时,究竟是什么负责解决这个问题呢？内核？或者C编译器在编译时对其进行排序？

我正在尝试构建一个通用树.Python中是否有内置的数据结构来实现树？

我最近在闲暇时间学习了不同的算法,而我遇到的似乎非常有趣的算法叫做HyperLogLog算法 - 它可以估算列表中有多少独特的项目.

这对我来说特别有趣,因为它让我回到了我的MySQL时代,当我看到"基数"值时(我总是假设它直到最近计算得不是估计的).

所以我知道如何在O(n)中编写一个算法来计算数组中有多少个唯一项.我用JavaScript写了这个:

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

但问题是我的算法,而O(n),使用了大量的内存(存储值Table).

我一直在阅读这篇论文,关于如何在O(n)时间内使用最少的内存来计算列表中的重复项.

它解释了通过散列和计数比特或某事物,可以在一定概率内(假设列表均匀分布)估计列表中的唯一项目的数量.

我读过这篇论文,但我似乎无法理解它.有人能给出更多非专业人士的解释吗？我知道什么是哈希,但我不明白它们如何在这个HyperLogLog算法中使用.

我有这个API函数:

public ResultEnum DoSomeAction(string a, string b, DateTime c, OtherEnum d, 
     string e, string f, out Guid code)

我不喜欢它.因为参数顺序变得不必要的重要.添加新字段变得更加困难.很难看到传递的是什么.将方法重构为较小的部分更加困难,因为它会产生另一个传递子函数中所有参数的开销.代码更难阅读.

我提出了一个最明显的想法:让一个对象封装数据并传递它,而不是逐个传递每个参数.这是我想出的:

public class DoSomeActionParameters
{
    public string A;
    public string B;
    public DateTime C;
    public OtherEnum D;
    public string E;
    public string F;        
}

这减少了我的API声明:

public ResultEnum DoSomeAction(DoSomeActionParameters parameters, out Guid code)

尼斯.看起来很无辜,但我们实际上引入了一个巨大的变化:我们引入了可变性.因为我们以前一直在做的事实上是传递一个匿名的不可变对象:堆栈上的函数参数.现在我们创建了一个非常可变的新类.我们创建了操纵调用者状态的能力.太糟糕了.现在我希望我的对象不可变,我该怎么办？

public class DoSomeActionParameters
{
    public string A { get; private set; }
    public string B { get; private set; }
    public DateTime C { get; private …

在Clojure中测试列表是否包含给定值的最佳方法是什么？

特别是,这种行为contains?目前令我感到困惑:

(contains? '(100 101 102) 101) => false

我显然可以编写一个简单的函数来遍历列表并测试相等性,但肯定有一种标准的方法可以做到这一点吗？

我有一个Java中的Hashmap,如下所示:

private Map<String, Integer> team1 = new HashMap<String, Integer>();

然后我这样填写:

team1.put("United", 5);

我怎样才能获得钥匙？像:team1.getKey()回归"联合国".

有没有人曾经实施过Fibonacci-Heap？几年前我这样做了,但它比使用基于阵列的BinHeaps要慢几个数量级.

那时候,我认为这是一个很有价值的教训,研究的结果并不像它声称的那样好.然而,许多研究论文声称他们的算法的运行时间基于使用Fibonacci-Heap.

你有没有设法产生有效的实施？或者你使用的数据集如此之大,以至于Fibonacci-Heap效率更高？如果是这样,一些细节将不胜感激.

我想记录一个对象占用多少内存(以字节为单位)(我正在比较数据结构的大小),似乎没有方法可以在Java中执行此操作.据说,C/C++有sizeOf()方法,但这在Java中是不存在的.我尝试Runtime.getRuntime().freeMemory()在创建对象之前和之后记录JVM中的空闲内存,然后记录差异,但它只会给出0或131304,而不管结构中的元素数量是什么.请帮忙!