1

私はアルゴリズムのコースを受講していて、行列を乗算するための Strassen のアルゴリズムについて学びました。これをノードに実装しましたが、小さな行列で動作します。非常に大きなマトリックスでテストしたいのですが、作成しようとするとノードのコア ダンプが発生します。サイズ 10000 の最初のマトリックスを作成できますが、2 番目のマトリックスを作成しようとするとクラッシュします。以下の完全なスタック トレース:

> const M2 = randomMatrix(10000);
undefined
> const M3 = randomMatrix(10000);

<--- Last few GCs --->

[55746:0x398dfc0] 614765011 ms: Mark-sweep 1318.6 (1439.7) -> 1318.6 (1439.7) MB, 528.7 / 0.0 ms  (average mu = 0.087, current mu = 0.000) allocation failure scavenge might not succeed
[55746:0x398dfc0] 614765516 ms: Mark-sweep 1318.6 (1439.7) -> 1318.6 (1439.7) MB, 505.1 / 0.0 ms  (average mu = 0.046, current mu = 0.000) last resort GC in old space requested


<--- JS stacktrace --->

==== JS stack trace =========================================

    0: ExitFrame [pc: 0x480f73dbe1d]
Security context: 0x26efb64f8041 <JSObject>
    1: randomMatrix [0x1ffe2ccfb921] [repl:~1] [pc=0x480f76ad37a](this=0x33298d21ad11 <JSGlobal Object>,n=10000)
    2: /* anonymous */ [0x1be321b7adb1] [repl:1] [bytecode=0x1be321b7ad41 offset=26](this=0x33298d21ad11 <JSGlobal Object>)
    3: InternalFrame [pc: 0x480f738ee75]
    4: EntryFrame [pc: 0x480f73892c1]
    5: ExitFrame [pc: 0x480f73dbe1d]
    6: r...

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory
 1: 0x8db900 node::Abort() [node]
 2: 0x8db94c  [node]
 3: 0xad6c1e v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [node]
 4: 0xad6e54 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [node]
 5: 0xec44e2  [node]
 6: 0xec45e8 v8::internal::Heap::CheckIneffectiveMarkCompact(unsigned long, double) [node]
 7: 0xed06c2 v8::internal::Heap::PerformGarbageCollection(v8::internal::GarbageCollector, v8::GCCallbackFlags) [node]
 8: 0xed0ff4 v8::internal::Heap::CollectGarbage(v8::internal::AllocationSpace, v8::internal::GarbageCollectionReason, v8::GCCallbackFlags) [node]
 9: 0xed2509 v8::internal::Heap::CollectAllAvailableGarbage(v8::internal::GarbageCollectionReason) [node]
10: 0xed3cce v8::internal::Heap::AllocateRawWithRetryOrFail(int, v8::internal::AllocationSpace, v8::internal::AllocationAlignment) [node]
11: 0xe9d0e4 v8::internal::Factory::NewFillerObject(int, bool, v8::internal::AllocationSpace) [node]
12: 0x113c88e v8::internal::Runtime_AllocateInNewSpace(int, v8::internal::Object**, v8::internal::Isolate*) [node]
13: 0x480f73dbe1d 
Aborted (core dumped)

マトリックスを作成するために使用するコードを含めています。

/*
input:  two integers, min and max.
output:  a random integer in [min, max]
*/ 
function randomInteger(min, max) { 
    return Math.floor(Math.random() * (max - min + 1)) + min; 
}

/* 
input:  an integer n. 
output:  an n x n matrix, randomly filled with integers in [0, 100] 
*/ 
function randomMatrix(n) { 
    const M = new Array(n).fill().map( () => Array(n).fill() );

    for(let i = 0; i < n; i++) {
     for(let j = 0; j < n; j++) {
         M[i][j] = randomInteger(0, 100);
        }
    }

 return M;
}

この問題の解決策はありますか?

4

1 に答える 1