node.js - 尝试在 Node Js 中消耗大量内存的实现
问题描述
以下是我在 node js 中的 Trie 实现。我正在加载一个在 Trie 中有大约 2.5L 行的文本文件。但是 trie 增长如此之快,以至于应用程序由于内存不足而崩溃。我正在加载的文件有键和值,我需要使用任何可能的平均值来找到特定对应键的值,但应该是最快的,因为我每小时要处理数百万条记录。
'use strict';
const config = require("../config/config");
const logger = config.appLogger;
const treemap = require("ts-treemap");
function newTrie() {
this.head = {
key : ''
, children: {}
}
}
newTrie.prototype.init = function(gts) {
var trieBckp = JSON.parse(JSON.stringify(this.head));
if (!gts) throw new Error("Invalid parameter [collection]");
try {
this.addAll(gts);
} catch (err) {
this.head = trieBckp;
throw err;
}
}
newTrie.prototype.addAll = function(gts){
for(let i=0; i < gts.length; i++){
this.addToTree(gts[i]);
}
}
newTrie.prototype.addToTree = function(obj){
logger.debug(`Object Add to Tree ${JSON.stringify(obj)}`);
let curNode = this.head;
let newNode = null;
let curChar = obj.KEY.slice(0,1);
let key = obj.KEY.slice(1);
while(typeof curNode.children[curChar] !== "undefined" && curChar.length > 0){
curNode = curNode.children[curChar];
curChar = key.slice(0,1);
key = key.slice(1);
}
while(curChar.length > 0) {
newNode = {
key : curChar,
value : key.length === 0 ? obj.GT : undefined,
children : {}
};
logger.debug(`New Node ${JSON.stringify(newNode)}`);
curNode.children[curChar] = newNode;
curNode = newNode;
curChar = key.slice(0,1);
key = key.slice(1);
}
logger.debug(`Trie after add ${JSON.stringify(this.head)}`);
}
newTrie.prototype.getTrie = function(key, mode) {
try {
let match = null;
if (!key) {
logger.error("Invalid parameter [key]");
return;
}
if (!mode) {
logger.error("Invalid parameter [mode]");
return;
}
if (key.length == 0) {
logger.error("getTrie parameter [key] is empty");
return;
}
if (this.head.size == 0) {
logger.error("getTrie trie is empty");
return;
}
if (mode == "bestMatch") {
var curNode = this.head
, curChar = key.slice(0,1)
, d = 0;
key = key.slice(1);
while(typeof curNode.children[curChar] !== "undefined" && curChar.length > 0){
curNode = curNode.children[curChar];
curChar = key.slice(0,1);
key = key.slice(1);
}
if (curNode.value != undefined && key.length === 0) {
match = curNode.value;
}
} else {
match = this.getTrie(key.slice(0,1));
}
if (match == null) {
logger.debug(`No match found for key ${key}`);
}
return match;
} catch (err) {
logger.error(`Error -${err}`);
throw err;
}
}
module.exports = newTrie;
解决方案
推荐阅读
- excel - 从 Excel VBA 创建和格式化 Word 表格时遇到问题
- javascript - Fetch 在 Postman 接受时返回内部服务器错误
- c# - 为什么 IEnumerable 不是由 string.Join 枚举的
- outlook - 将 Internet 日历与所有设备(智能手机)的 office 365 日历同步
- javascript - 使用导出的 Firebase 作为全局对象是否安全
- excel - 如何使用 VBA 用 aspx 代码抓取网页?
- java - Camel:跳过固定长度文件中的多个标题行返回迭代器对象引用
- php - Symofny 3 - parent::__construct() 无法注入
- mysql - Mysql:使用大小写仅列出不为空的值
- c++ - 是否可以等待从暂存缓冲区的传输完成而不调用 vkQueueWaitIdle