小编dsi*_*cha的帖子

我现在的主要语言是D,我正在学习Python,因为这是我正在学习的课程所必需的.虽然我理解为什么动态语言会让人们在没有类型推断或模板的情况下使用静态语言进行编程(IMHO模板在很大程度上是编译时的鸭子打字),但我很好奇动态语言的好处是什么即使你有那些.

最重要的是,如果我要学习Python,我想以一种真正改变我对编程思路的方式来学习它,而不仅仅是在Python中编写D.我没有使用动态语言,因为我是一个相当新手的程序员,无法欣赏他们所提供的灵活性,并希望学会现在充分利用它们.在静态语言中,即使使用模板,多态,静态类型推断以及可能的运行时反射,在动态类型化的解释语言中,可以轻松/优雅地完成哪些操作？

我已经向D编程语言运行时的维护者建议了几次内存分配器/垃圾收集器应该使用自旋锁而不是常规的OS关键部分.这并没有真正流行起来.以下是我认为自旋锁更好的原因:

1. 至少在我所做的综合基准测试中,当存在内存分配器/ GC锁争用时,它比OS关键部分快几倍.编辑:根据经验,使用自旋锁在单核环境中甚至没有可测量的开销,可能是因为锁需要在内存分配器中保持如此短的时间.
2. 内存分配和类似操作通常只需要一小部分时间片,甚至是上下文切换所花费的一小部分时间,这使得在争用情况下上下文切换变得愚蠢.
3. 无论如何,有问题的实现中的垃圾收集会阻止世界.在收集过程中不会有任何旋转.

有没有充分的理由不在内存分配器/垃圾收集器实现中使用自旋锁？

我希望在性能关键代码中多次计算熵和互信息.作为中间步骤,我需要计算每个值的出现次数.例如:

uint[] myArray = [1,1,2,1,4,5,2];
uint[] occurrences = countOccurrences(myArray);
// Occurrences == [3, 2, 1, 1] or some permutation of that.
// 3 occurrences of 1, 2 occurrences of 2, one each of 4 and 5.

当然,显而易见的方法是使用关联数组或使用"标准"排序算法(如快速排序)对输入数组进行排序.对于小整数,如字节,代码目前专门用于使用普通的旧数组.

是否有任何聪明的算法比哈希表或"标准"排序算法更有效地做到这一点,例如一个非常有利于插入更新的关联数组实现,或者当你的数据有很多关系时会发光的排序算法？

注意:非稀疏整数只是可能数据类型的一个示例.我想在这里实现一个合理的通用解决方案,但由于只包含整数的整数和结构是常见的情况,如果它们非常有效,我会对这些特定的解决方案感兴趣.

是否存在任何现代的通用CPU,从不同的线程同时写入数组的相邻元素是不安全的？我对x86特别感兴趣.你可以假设编译器没有做任何明显荒谬的事情来增加内存粒度,即使它在技术上是在标准范围内.

我对编写任意大型结构的情况感兴趣,而不仅仅是本机类型.

注意:

请不要提及有关虚假共享的性能问题.我很清楚这些,但它们对我的用例没有实际意义.我也知道从除读者之外的线程写入的数据的可见性问题.我的代码解决了这个问题.

澄清:出现这个问题是因为在某些处理器(例如,旧的DEC Alphas)上,内存只能在字级处理.因此,以非字大小增量(例如,单个字节)写入存储器实际上涉及要写入的字节的读 - 修改 - 写入以及引擎盖下的一些相邻字节.要想象这一点,请考虑写入单个位所涉及的内容.你读取了字节或单词,对整个事物执行按位操作,然后将整个事情写回来.因此,您无法安全地从不同的线程写入相邻的位.

理论上,当硬件不需要时,编译器也可以通过这种方式实现内存写入,这在理论上是可行的,尽管非常愚蠢.x86可以解决单个字节,所以它主要不是问题,但我想弄清楚是否有任何奇怪的角落情况.更一般地,我想知道,如果写在不同的线程的阵列的相邻元件仍然是一个现实的问题或大多只是一种理论上只适用于掩盖/古硬件和/或很奇怪的编译器.

又一个编辑:这是一个很好的参考,描述了我正在谈论的问题:

http://my.safaribooksonline.com/book/programming/java/0321246780/threads-and-locks/ch17lev1sec6

假设我有一组字符串S和一个查询字符串q.我想知道S的任何成员是否是q的子串.(出于这个问题的目的,substring包含相等,例如"foo"是"foo"的子串.)例如,假设执行我想要的函数被调用anySubstring:

S = ["foo", "baz"]
q = "foobar"
assert anySubstring(S, q)  # "foo" is a substring of "foobar"

S = ["waldo", "baz"]
assert not anySubstring(S, q)

是否有任何易于实现的算法来实现时间复杂度为子线性len(S)？如果必须首先将S处理成一些聪明的数据结构,这是可以的,因为我将使用大量q字符串查询每个S,因此这种预处理的摊销成本可能是合理的.

编辑:为了澄清,我不关心S的哪个成员是q的子串,只是至少有一个是.换句话说,我只关心布尔答案.

在Python中,str(),int(),float()等函数通常用于执行类型转换.但是,这些要求您在开发时了解要转换为的类型.我正在尝试编写的一些Python代码的子问题如下:

给出两个变量,foo并bar找到类型foo.(在开发时不知道,因为这是通用代码.)然后,尝试转换bar为任何类型foo.如果无法做到这一点,请抛出异常.

例如,假设您调用执行此操作的函数conv.它的签名看起来像

def conv(foo, bar) :
    # Do stuff.

它会被称为:

result = conv(3.14, "2.718")  # result is now 2.718, as a float.

给定一个长字符串L和一个较短的字符串S(约束是L.length必须> = S.length),我想找到长度等于.length的S任何子字符串之间的最小汉明距离.我们为此调用函数.例如,LSminHamming()

minHamming(ABCDEFGHIJ, CDEFGG) == 1.

minHamming(ABCDEFGHIJ, BCDGHI) == 3.

以明显的方式执行此操作(枚举L的每个子字符串)需要O(S.length*L.length)时间.在次线性时间有没有聪明的方法可以做到这一点？我L用几个不同的S字符串搜索相同的字符串,因此L可以接受一次复杂的预处理.

编辑:修改过的Boyer-Moore是个好主意,除了我的字母表只有4个字母(DNA).

我需要一个内存块的比较函数,用于对D编程语言中的字节数组进行二进制搜索.它不需要任何有用的语义.它只需要很快并且是一个有效的比较函数(产生总排序的函数).已知要比较的存储器块具有相同的长度.

C memcmp实际上非常慢,因为它试图保留有用的字符串比较语义,这是我不需要的.以下是迄今为止我提出的最佳方法.有没有人知道更好的事情,最好不要使用非便携式CPU特定指令？

// Faster than C's memcmp because it doesn't preserve any meaningful
// semantics.  It's just a completely arbitrary, but really fast,
// comparison function.
int memoryCompare(const(void)* lhs, const(void)* rhs, size_t n) {
    for(; n >= uint.sizeof; n -= uint.sizeof) {
        if( *(cast(uint*) lhs) < *(cast(uint*) rhs)) {
            return -1;
        } else if( *(cast(uint*) lhs) > *(cast(uint*) rhs)) {
            return 1;
        }
        lhs += uint.sizeof;
        rhs += uint.sizeof;
    }

    for(; n >= ubyte.sizeof; n -= ubyte.sizeof) { …

根据各种来源,例如维基百科和谷歌发现的各种.edu网站,哈希表解决冲突的最常见方式是线性或二次探测和链接.简要提及随机探测,但没有给予太多关注.我已经实现了一个使用随机探测来解决冲突的哈希表.假设存在冲突,解决方案的工作方式如下:

1. 对象的完整(32位)散列用于为线性同余随机数生成器设定种子.
2. 生成器生成32位数字,并采用模数来确定哈希表中接下来要探测的位置.

这具有非常好的属性,无论模数空间中有多少哈希冲突,只要在完整的32位哈希空间中存在很少的冲突,查找和插入时间预期为O(1).由于探测序列是伪随机的,因此与线性探测不同,模数空间碰撞不会产生聚类行为.由于整个系统是开放式地址,并且不在任何地方使用链接列表,因此与链接不同,您不需要在每次插入时执行内存分配.

此外,因为散列的大小通常是地址空间的大小(32位机器上的32位),所以根本不可能在地址空间中容纳足够的项以在完整的32位散列中导致大量的散列冲突良好的哈希方案下的空间.

那么,为什么随机探测这种不受欢迎的碰撞解决策略呢？

对于那些不熟悉D字符串mixins的人来说,它们基本上是编译时间的.您可以获取任何编译时字符串(无论是文字还是通过模板元编程或编译时函数评估生成)并将其编译为代码.如果你使用一个简单的字符串文字,它基本上是编译器自动复制粘贴.

您是否认为使用字符串混合文字作为简单代码重用的方法是反模式,而其他分解方法不太合适？一方面,它基本上是编译器自动化的文字复制和粘贴,这意味着一旦混合在实例中就没有任何关系.如果字符串mixin中的符号与混合范围中的符号发生碰撞,则会发生错误(尽管在编译时,而不是在运行时).它是相对非结构化的,例如,可以将一个字符串混合到一个函数的中间,当且仅当范围中的变量根据某个约定命名时才会起作用.Mixins还可以声明外部作用域随后可以使用的变量.

另一方面,因为复制和粘贴是编译器自动化的,所以在源代码级别的代码有一个单一的真实点,如果需要修改它,它只需要在一个地方修改,一切都保持同步.字符串mixins还大大简化了重用代码,这些代码很难以任何其他方式考虑因素,否则很有可能被手动剪切和粘贴.