非重复随机数生成方法

摘要

本发明涉及非重复随机数生成方法，和涉及利用这样的方法读写记录媒体的设备。根据本发明，从项目表中选择项目的随机数生成方法包括如下步骤：随机抽取(1)数字X，其中X在来自项目表的还未选择项的‘1’到数字‘M’的范围内；遍查(5)项目表找出X-位置的未选择项；和输出(6)X-位置的未选择项。

权利要求

1.一种从项目表中选择项目的随机数生成方法，该方法包括步骤：-随机抽取(1)数字X，其中X在来自项目表的还未选择项的‘1’到数字‘M’的范围内；

-遍查(4)项目表找出X-位置的未选择项；和-输出(3)X-位置的未选择项。

2.根据权利要求1所述的方法，其中，遍查项目表找出X-位置的未选择项的步骤包括：-将项目表划分成多个分段；

-定义分段计数器Cn，其中，Cn的值表示第n分段中未选择项的个数；

-利用随机数X和分段计数器Cn确定(5)目标分段S和这个分段中的目标项Y；和-遍查(6)目标分段S找出Y-位置的未选择项。

3.一种从项目表中选择项目的随机数生成方法，该方法包括步骤：-将项目表划分成多个分段；

-定义分段计数器Cn，其中，Cn的值表示第n分段中未选择项的个数；

-通过随机抽取第一数字Z确定(7)目标分段S，其中Z在包括至少一个未选轨道的分段的‘1’到数字‘Q’的范围内；

-通过在确定分段的‘1’到计数器值‘Cn’的范围内生成第二随机数Y，在确定分段中确定(8)目标项Y；和-遍查(6)目标分段S找出Y-位置的未选择项。

4.根据权利要求1到3之一所述的方法，进一步包括如下步骤：-根据与项目相联系的至少-条选择准则，从项目表中生成项目子表；和-只对项目子表进行随机数生成。

5.根据权利要求4所述的方法，其中，元数据用作选择准则。

6.根据权利要求1、2、3、5之一所述的方法，其中，项目是多媒体文件。

7.根据权利要求4所述的方法，其中，项目是多媒体文件。

8.根据权利要求4所述的方法，其中，选择准则是将多媒体文件加入特定文件夹、或选择的文件夹、或用户定义程序表。

9.一种回放多媒体文件的设备，其特征在于，它为多媒体文件的随机回放生成一系列非重复数字，所述设备包括：-用于随机抽取数字X的部件，其中X在来自项目表的还未选择项的‘1’到数字‘M’的范围内；

-用于遍查项目表找出X-位置的未选择项的部件；和-用于输出X-位置的未选择项的部件。

10.根据权利要求9所述的设备，其中，用于遍查项目表找出X-位置的未选择项的部件包括：-用于将项目表划分成多个分段的部件；

-用于定义分段计数器Cn的部件，其中，Cn的值表示第n分段中未选择项的个数；

-用于利用随机数X和分段计数器Cn确定目标分段S和这个分段中的目标项Y的部件；和-用于遍查目标分段S找出Y-位置的未选择项的部件。

11.一种回放多媒体文件的设备，其特征在于，它为多媒体文件的随机回放生成一系列非重复数字，所述设备包括：-用于将项目表划分成多个分段的部件；

-用于定义分段计数器Cn的部件，其中，Cn的值表示第n分段中未选择项的个数；

-用于通过随机抽取第一数字Z确定目标分段S的部件，其中Z在包括至少一个未选轨道的分段的‘1’到数字‘Q’的范围内；

-用于通过在确定分段的‘1’到计数器值‘Cn’的范围内生成第二随机数Y，在确定分段中确定目标项Y的部件；和-用于遍查目标分段S找出Y-位置的未选择项的部件。

12.根据权利要求9到11之一所述的设备，进一步包括：-用于根据与项目相联系的至少一条选择准则，从项目表中生成项目子表的部件；和-用于只对项目子表进行随机数生成的部件。

13.根据权利要求12所述的设备，其中，元数据用作选择准则。

14.根据权利要求9、10、11、13之一所述的设备，其中，项目是多媒体文件。

15.根据权利要求12所述的设备，其中，项目是多媒体文件。

16.根据权利要求12所述的设备，其中，选择准则是将多媒体文件加入特定文件夹、或选择的文件夹、或用户定义程序表。

说明书

技术领域

本发明涉及非重复随机数生成方法，和涉及利用这样的方法读写记录媒体的设备。

背景技术

随机数发生器用于随机回放存储在诸如CD(光盘)之类的光记录媒体上的声道。一般说来，用户不想以真正随机的顺序收听轨道，因为这会导致一些轨道被重复收听。取而代之，所有轨道应该以随机顺序只回放一次。因此，一般要使用非重复随机数发生器。
简单非重复随机数发生器实现如下。在第一步骤中，随机抽取数字X，其中X在开始轨道和结束轨道之间的范围内。在第二步骤中，检验数字X以前是否生成过。如果情况不是这样，将数字X用于回放。否则，随机抽取新的数字X，直到获得以前没有生成过的数字X。
上面的发生器存在两个缺点。尽管它比较适用于小数据集，通常小于100个项目，但当数据集的规模变大时，性能显著下降。这是由于已经回放过的项目越多，需要随机抽取获得以前没有生成过的数字的次数就越多。另外，这种发生器的性能是真正随意的和不可预测的。
当必须随机抽取数量非常大的项目时，这两个主要缺点使这种类型的简单非重复随机数发生器通常无法付诸使用，当像处理时间那样的资源要求是主要关心对象时，这极大地阻碍了它的应用。对于，例如，能够回放压缩音频文件(MP3文件等)或压缩静止图像(JPEG(联合图像专家组)文件等)的设备，情况亦如此。由于压缩，大量文件可以存储在存储媒体上，例如，几千张静止图像存储在单个光盘或存储卡上，或甚至更多的文件存储在硬盘上。

发明内容

本发明的目的是提出非重复随机数生成的新方法，它能够管理极大量项目同时时间要求显著地改善。
根据本发明，这个目的是通过从项目表中选择项目的随机数生成方法实现的，该随机数生成方法包括如下步骤：
-随机抽取数字X，其中X在来自项目表的还未选择项的‘1’到数字‘M’的范围内；
-遍查项目表找出X-位置的未选择项；和
-输出X-位置的未选择项。
可以看出，这种方法不需要重复地随机抽取和搜索未选择项，因此，性能是可预测的。尽管这种方法比现有技术中已知的方法快得多，但当项目表变得非常大时，性能仍然下降。这种下降主要来源于每次找出未选择项都要遍查整个项目表。
根据本发明的进一步改进，通过如下步骤优化遍查项目表找出X-位置的未选择项的步骤的速度：
-将项目表划分成多个分段；
-定义分段计数器Cn，其中，Cn的值表示第n分段中未选择项的个数；
-利用随机数X和分段计数器Cn确定目标分段S和这个分段中的目标项Y；和
-遍查目标分段S找出Y-位置的未选择项。
这是一种生成非重复随机数的有效和高效方法。这种速度优化方法的关键是项目表分段和将计数器与每个分段相联系。这样，从与目标较接近的位置开始搜索未选择项，从而缩短了搜索时间。另外，即使项目表的规模显著增大，这种方法的性能也不会下降。
根据本发明的另一个方面，这个目的也是通过从项目表中选择项目的随机数生成方法实现的，该随机数生成方法包括如下步骤：
-将项目表划分成数个分段；
-定义分段计数器Cn，其中，Cn的值表示第n分段中未选择项的个数；
-通过随机抽取第一数字Z确定目标分段S，其中Z在包括至少一个未选轨道的分段的‘1’到数字‘Q’的范围内；
-通过在确定分段的‘1’到计数器值‘Cn’的范围内生成第二随机数Y，在确定分段中确定目标项Y；和
-遍查目标分段S找出Y-位置的未选择项。
此外，在这种方法中，也只需遍查项目表的单个分段，与遍查整个项目表直到X-位置的未选择项相比，缩短了找出X-位置的未选择项的时间。
最好，根据本发明的方法进一步包括如下步骤：
-根据与项目相联系的至少一条选择准则，从项目表中生成项目子表；和
-只对项目子表进行随机数生成。
这种方法的优点在于，用户可以指定只选择特定类型的项目。例如，用户可能希望只选择特定日期之后(或之前)加入或存储、在某个时期内编辑等的项目。哪些项目对应于选择准则可以利用与项目相联系的元数据确定。在这些项目是多媒体文件的情况下，选择准则也可以是文件的类型，譬如，音频文件、图像文件、视频文件或文本文件。另外，选择准则也可以是将多媒体文件加入特定文件夹中或文件夹的选择。在这种情况下，只选择存储在特定文件夹中的文件。取决于如何实现，这也可以包括子文件夹中的文件。类似地，将多媒体文件加入用户定义程序表中可以用于生成能在定义的用户选择内随机回放的子表。
最好，根据本发明的方法用于在读取和/或写入记录媒体的设备中，为多媒体文件，例如，MP3文件或JPEG文件的随机回放生成一系列非重复数字，所述设备包括：用于随机抽取数字X的部件，其中X在来自项目表的还未选择项的‘1’到数字‘M’的范围内；用于遍查项目表找出X-位置的未选择项的部件；和用于输出X-位置的未选择项的部件。多媒体文件可以存储在，例如，诸如存储卡或光盘之类的可移动存储媒体上，或诸如RAM(随机访问存储器)或硬盘驱动器之类的设备内部存储器中。也可以将本发明推广到在通过随机数生成确定文件之后向服务器请求所选多媒体文件的没有存储器的设备。在所有这样的设备中，确定下一个随机多媒体文件所需的时间需要忽略不计。否则，可能满足不了这样设备的用户。

附图说明

为了更好地理解本发明，现在参照附图，在如下的描述中更详细地说明本发明。应该明白，本发明不局限于这个示范性实施例，也可以方便地组合和/或修改具体特征，而不偏离本发明的范围。在附图中：
图1a)、1b)示出了根据现有技术的非重复随机数生成方法；
图2a)、3b)示出了根据本发明的非重复随机数生成方法；
图3a)、3b)示出了根据本发明的速度优化的非重复随机数生成方法；
图4描述了根据本发明的可替代的速度优化的非重复随机数生成方法；和
图5例示了可选项目子表的生成。

具体实施方式

尽管在下文中利用记录媒体上的轨道的例子说明本发明，但本发明的使用理所当然不局限于这个例子。本发明可应用于必须不重复地从项目表中随机选择项目的任何情形。
在图1a)中，描绘了根据现有技术的非重复随机数生成方法。在第一步骤1中，随机抽取数字X。数字X在开始轨道号‘1’和结束轨道号‘N’之间的范围内。在下一个步骤2中，检验数字X以前是否生成过，即，带有数字X的轨道是否已经被选择过。如果情况不是这样，回放(3)轨道号X。否则，随机抽取(1)新的数字X，直到获得以前没有生成过的数字X。
图1b)描述了这种非重复随机数生成方法的轨道表。在第一列中，列出了从轨道1到轨道N的可用轨道。已经选择过的轨道用斜体示出。第二列表示为了选择特定轨道必须生成的随机数。从表中可以看出，一些可能随机数与已经回放过的轨道相联系。在出现这样随机数的情况下，必须生成新随机数。生成还没有使用的随机数的概率随剩余轨道的数量减少而降低。
根据本发明的非重复随机数生成方法例示在图2a)中。与前面一样，在第一步骤(1)中，随机抽取数字X。但是，在这种情况下，X在来自轨道表的还未选择轨道的‘1’到数字‘M’的范围内。当已经生成随机数X时，遍查(4)轨道表找出目标轨道X，即，X-位置未选轨道。然后，回放这个轨道。
从图2b)中可以看出，每个随机数X与一个未选轨道相联系。因此，不再有必要生成另外随机数。取而代之，每当生成轨道数时，就将随机数的目标范围‘1’到‘M’减‘1’。
导致方法的速度优化的本发明的进一步改进显示在图3a)中。正如在图3b)的表中的第3列‘S’所指的那样，这种改进包括轨道表变成小段‘1’到‘P’的分段。在本例中，每个分段包括4个轨道。当然，其它轨道数也同样是可以的。甚至没有必要对所有分段使用相同的轨道数。如表的第4列所示，每个分段拥有相关的分段计数器Cn，它的值表示第n分段中的未选择项数。
此外，在第一步骤(1)中，随机抽取数字X，数字X在来自轨道表的还未选择轨道的‘1’到数字‘M’的范围内。根据随机数X，确定(5)目标分段S和这个分段中的目标轨道Y(表的第5列所指)。这可以通过，例如，计算
$\underset{n=1}{\overset{m}{\Sigma }}{C}_n$
和确定总和超过X的计数器值m完成。然后，目标分段是分段m。在这种情况下分段S中的目标项Y是
$Y=X-\underset{n=1}{\overset{m-1}{\Sigma }}{C}_n$
在接着的步骤(6)中，遍查目标分段S，找出Y-位置的未选择项，然后回放(3)Y-位置的未选择项。由于在步骤(6)中只需遍查一段轨道表，而不是整个轨道表，找出Y-位置未选轨道的时间缩短了。
如图4所示，取代在还未选择轨道的‘1’到数字‘M’的范围内随机提取X和随后确定相应目标分段S和目标轨道Y，也可以在包括至少一个未选轨道，即，具有计数器值Cn＞0的分段的‘1’到数字‘Q’的范围内生成第一随机数Z，然后，通过在所选分段的‘1’到计数器值‘Cn’的范围内生成第二随机数获得目标轨道号Y。此外，为了找出所选轨道，只需遍查单个分段。
图5例示了轨道子表的生成。在图5左侧的轨道表中，第2列表示对于某个轨道，是否满足特定选择准则sel。然后，在描绘在图5右侧的、和是非重复随机数生成的基础的选择表中标记满足选择准则的轨道。选择准则可以是，例如，‘已经被用户1存储的轨道’，或‘在至少一个月内未曾回放的轨道’等。尤其，在轨道是存储在，例如，硬盘或存储卡上的数据文件的情况下，可获得可用作选择准则的多个这样元数据项。另外，在以文件夹结构安排轨道的情况下，选择准则也可以是‘文件夹XYZ中的轨道’，即，只选择存储在特定文件夹中的轨道。取决于如何实现，这也可以包括子文件夹中的轨道。类似地，用户定义回放程序也可以用作子表。