如何快速生成1000万个唯一数字Groovy/Java

nnsrf1az  于 8个月前  发布在  Java
关注(0)|答案(5)|浏览(83)

下面的代码花了5个小时才完成1米,哈哈,这太慢了。

int numbers = 10000000
int count = 0
def data = []
File file = new File("out.txt")

while (count < numbers) {
    def number = makeNumber(numbers)
    if (!data.contains(number)) {
        print count + ':Adding ' + number + '\n'
        data << number
        count++
    }
}

for (i in data) {
    print 'Appending ' + i + '\n'
    file.append(i + '\n')
}

String makeNumber(numbers) {
    def range = "83"
    return range + (new Random().nextInt(20000000) + numbers)
}

我目前正在尝试java.security.SecureRandom作为在this request生成的数字,但它是一个未知的API给我,所以它是缓慢的。很多其他的选择并不能保证唯一性或速度。我有独特性下来,我很肯定,但速度(请你能扔给我一些想法,以加快这一点?我在考虑发送到其他线程,但我会遇到同样的问题,不是吗?).

dfuffjeb

dfuffjeb1#

tl;dr

在Java语法中:

List < String > range =
        IntStream
                .range ( 10_000_000 , 20_000_000 )   // Generate a sequence of all desired values, rather than generate random numbers.
                .mapToObj ( ( int i ) -> "83" + i )  // Convert from `int` primitive to `String` object, and prepend "83". 
                .collect ( Collectors.toCollection ( ArrayList :: new ) );
Collections.shuffle ( range , random );
Files.write ( Paths.get ( "/tmp/numbers.txt" ) , range );

在笔记本电脑上执行时间为242-3秒
或者,我们可以尝试这个漂亮的几乎一行的基础上评论约翰内斯库恩。但这需要更长的时间,在3.5到4.5秒的时间内,需要两倍以上的时间。

try
{
    Files.write (
            Paths.get ( "/tmp/numbers.txt" ) ,
            SecureRandom
                    .getInstance( "NativePRNG" )
                    .ints ( 0 , 20_000_000 )
                    .distinct ( )
                    .limit ( 10_000_000 )
                    .mapToObj ( ( int i ) -> "83" + i )
                    .toList ( )
    );
}
catch ( IOException e ) { throw new RuntimeException ( e ); }

生成一个数字序列,而不是随机数

显然你想要一千万到两千万之间的一千万个数字。请注意,这仅仅意味着范围 * 从 * 10,000,000到20,000,000。您的可能值范围等于您的期望结果范围。所以我们可以从组装一个1000万到2000万的序列开始。
我们使用IntStream.range将数字序列组装为int值流。
你说你想把每个数字都当作文本,并在文本"83"之前加上前缀。因此,我们使用Stream::map将每个数字与prepend一起沿着转换为文本。
我还不知道Groovy,所以我将使用Java语法。

List < String > range =
        IntStream
                .range ( 10_000_000 , 20_000_000 )
                .mapToObj ( ( int i ) -> "83" + i ) 
                .collect ( Collectors.toCollection ( ArrayList :: new ) );

报告要验证的第一个和最后一个值。

System.out.println ( range.get ( 0 ) + " - " + range.get ( range.size ( ) - 1 ) );

你想要这一千万个随机排列的字符串。所以调用Collections.shuffle来随机重新排序它们。不需要生成随机数。

Collections.shuffle ( range );

报告要验证的第一个和最后一个值。

System.out.println ( range.get ( 0 ) + " - " + range.get ( range.size ( ) - 1 ) );

运行时:

8310000000 - 8319999999
8315634260 - 8311372639

强随机数生成器

如果您需要一个比默认情况下提供的更强的加密随机数生成器来执行 Shuffle ,您可以传递一个替代的随机性源。它可以是Random或任何子类,包括SecureRandom。举例来说:

Collections.shuffle ( 
    range , 
    SecureRandom.getInstance( "DRBG" ) 
);

我不是随机数生成器的Maven。但我猜这些可能对你感兴趣:

我从这些文档中了解到,通过Java Service provider interfaceSecureRandomSpi类,除了与某些JDK捆绑在一起的新的和改进的实现之外,还可以插入第三方生成器实现。

写文件

你说你需要把这些写进一个文件。字符串的List本身就是一个Iterable。因此,我们只能传递给Files.write,这是现代文件处理类的Java NIO包中的一个方法。

try
{
    Files.write (
            Paths.get ( "/tmp/numbers.txt" ) ,
            range
    );
}
catch ( IOException e ) { throw new RuntimeException ( e ); }
}

生成的文件大小为110 MB。

性能

你需要一点空闲内存来运行上面的代码。我们在写入存储之前在内存中创建所有数据。考虑到上面报告的文件大小,我猜它需要大约200到300 MB的RAM。
你关心的是执行速度。所以让我们运行一次,然后运行几次,以获得平均运行时间。对于更严格的基准测试,使用JMH

app.randomWrite ( );

int repetitions = 10;
List < Duration > durations = new ArrayList <> ( repetitions );
for ( int index = 0 ; index < repetitions ; index++ ) durations.add ( app.randomWrite ( ) );
System.out.println ( "durations = " + durations );

当在配备Apple M1 Pro芯片、16 GB内存和内部固态存储的Apple MacBook Pro上运行时,执行时间约为2.5秒,范围为2-3秒。

durations = [PT2.501965458S, PT2.315898625S, PT2.398674875S, PT2.24017325S, PT2.047942S]
iecba09b

iecba09b2#

下面的groovy代码需要大约2.5秒来生成1000万个唯一整数。

@groovy.transform.CompileStatic
Set<Integer> generateUniqueNumbers(int count, int bound=20000000, SplittableRandom rnd = new SplittableRandom()) {
    Set<Integer> data = new HashSet<Integer>(count)
    while(data.size() < count){
        data.add( rnd.nextInt(bound) )
    }
    return data
}

@groovy.transform.CompileStatic
def writeToFile(Set<Integer> data, String path){
    new File(path).withWriter("UTF-8"){w->
        data.each{i-> w.append('83').append(i.toString()).append('\n')}
    }
}

def t = System.currentTimeMillis()
def data  = generateUniqueNumbers(10000000)
println data.size()
println "generate time = ${System.currentTimeMillis() - t} millis"

//writing to file
t = System.currentTimeMillis()
writeToFile(data, "/11/out.txt")
println "write time = ${System.currentTimeMillis() - t} millis"

结果:

10000000
generate time = 2636 millis
write time = 2182 millis

如果生成的数字的顺序很重要-您可以使用LinkedHashSet而不是HashSet,但这将增加执行时间约x2 - x3
注意@groovy.transform.CompileStatic annotation -当性能很重要并且你有一个大的/长的循环时,总是尝试在groovy中使用它。

**UPD:**使用SplittableRandom而不是Random,因为它更快
**示例2:**增加了使用writer写入文件的方法。原问题File.append(...)中的实现每次打开和关闭文件。

to94eoyn

to94eoyn3#

如果data是一个集合。在数组中搜索每个随机数,其复杂度为O(N),在集合中搜索的复杂度为O(1)。
做N + c个随机化(c =随机化时的重复数)本身就是一个O(N)的复杂度,所以如果我们只考虑这个方面,暂时忽略其他一切,那么你就有了一个O(N^2)的算法,可以简单地通过切换到集合来简化为O(N)的算法。
如果可能的话,你也应该去掉控制台的指纹。这些都是昂贵的操作。文件写入也是如此。
您应该缓存最新的几个数字并将它们存储到输出文件中。可能有100个数字。然后你也可以在控制台中写入这些数字被添加。

pzfprimi

pzfprimi4#

只需大约14秒,我的核心i5与8Gb RAM创建40Mb的数字文件。如果您需要它们作为文本,最好在需要时将它们重新创建为文本。

import java.security.SecureRandom;
import java.nio.file.Path;
import java.nio.file.Files;
import java.nio.file.StandardOpenOption;
import java.nio.channels.FileChannel;
import java.nio.MappedByteBuffer;
import java.util.Set;
import java.util.HashSet;
import java.util.EnumSet;

public class Rands {
    public static void main(String[] args) throws Exception {
        final int NUMBERS = 10_000_000;
        final int MAX = 20_000_000;
        final int MIN = 83;
        Set<Integer> numbers = new HashSet<>(MAX - MIN);

        SecureRandom r = new SecureRandom();
        while (numbers.size() < NUMBERS) {
            numbers.add(r.nextInt(MIN, MAX));
        }

        Path pathToWrite = Path.of("numbers.bin");

        try (FileChannel fileChannel = (FileChannel) Files.newByteChannel(pathToWrite,
                EnumSet.of(StandardOpenOption.CREATE, StandardOpenOption.READ, StandardOpenOption.WRITE, StandardOpenOption.TRUNCATE_EXISTING))) {

            MappedByteBuffer mappedByteBuffer = fileChannel.map(FileChannel.MapMode.READ_WRITE, 0, numbers.size() * 4);

            if (mappedByteBuffer != null) {
                numbers.stream()
                    .forEach(n ->mappedByteBuffer.putInt(n));
            }
        }
    }
}
42fyovps

42fyovps5#

来自@daggert的回答被接受了,但它不符合我的要求。当尝试它给像1的数字,我需要一个集的大小。它被接受是因为我不清楚这一点,老实说,它的工作就像一个魅力。我使用文件编写部分与我写的集合代码混合,这在20秒内完成了我需要的工作。

int amountToGenerate = 10_000_000
int range = amountToGenerate*2
Set data = []
Random randoms = new Random()

while (data.size() < amountToGenerate){
    int number = randoms.nextInt(range)+amountToGenerate
    data.leftShift(number)
}

@groovy.transform.CompileStatic
def writeToFile(Set<Integer> data, String path){
    new File(path).withWriter("UTF-8"){w->
        data.each{i-> w.append('83').append(i.toString()).append('\n')}
    }
}
writeToFile(data, /c:\temp\out.txt/)

相关问题