Java算法设计:迭代器实现排序(求各位大佬各抒己见) 80C

老师预留的习题,说可能会考。希望能得到比较准备的回答用以备考。

假设你有M个迭代器(Java.util.Iterator),其中每一个迭代器定义为:由多个低成本基础迭代器组成,形成一个迭代器链(chain of Iterator),我们称之为resultant Iterator。每个resultant Iterator传递一个有序数据流。我们需要将这些数据流合并成一个最终有序数据流。

数据:每个数据由一串K个Key的序列组成 [k1,k2,k3,…,kK]
数据排序的规则为:最先排列k1,其次k2再次k3,……例如 [2,3,1,…] > [2,1,3,…] > [1,3,2,…]。每种key的排列在一个resultant Iterator中只会出现一次,但是多个resultant Iterator中可能出现相同的排列。

  • 问题A:为了便于分析,我们假设每个resultant Iterator返回N个元素,设计一种算法,能得到最终有序数据流,同时效率高于 O(N.M.K.lg(M)). 并且计算所设计算法的复杂度。(可以设计你需要的变量和参数)。如果有多种算法,请简述各自的优劣。

  • 问题B:简述如何重新设计迭代器,可以降低计算成本。为什么?

  • 问题C:若要在数据库中存储不可变的有序数据集(如本题中的数据),什么数据结构最为合适,为什么?若本题数据中所有的key都可以在byte的量级进行排序,例如有2个key,他们的排序根据他们第一个不同的byte进行排序。那对我们之前选择的数据结构有影响吗?若只有部分key可以又会怎么样?

  • 问题D:基于Java的思想,如何优化它在内存中的表示。为什么?

2个回答

如果你每个迭代器都是有序的,那么连起来就是归并排序。然后就是如果你的比较操作也花费成本,就要实现hash算法。
内存和数据库(文件系统)优化的方式不同,因为内存是随机访问的,可以考虑使用最小堆。数据库可以用排序索引。

讲道理,我没有读懂你数据和数据排序规则

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!