1

我正在尝试对从客户那里收到的对象进行分类。

在服务器端，我已经定义了我的“蓝图”，如下所示：

{ // "type1"
    type: 1,
    name: String,
    password: String
}

{ // "type2"
    type: 2,
    user_id: Number,
    action: String
}

{ // "type3", and yes, this says type: 2....
    type: 2,
    object_id: Number,
    action: String
}

根据客户发送的内容，我想将它们分类如下：

{ type: 1, name: 'user', password: 'pass' }                    // -> type1
{ type: 1, name: 'user', password: 'pass', remember_me: true } // -> type1
{ type: 2, name: 'user', password: 'pass' }                    // -> N/A
{ type: 2, user_id: 5, action: 'hello' }                       // -> type2
{ type: 2, object_id: 5, action: 'hello' }                     // -> type3

识别需要基于键名、值的数据类型和值的实际值。每秒将发送数千个对象，并且可能有数千个蓝图。< O(n)因此，如果可以在其中 n 是蓝图的数量时完成，那就太好了。

我是从头开始编写的，因此可以将蓝图和元数据存储在所需的任何数据结构中。

谢谢您的帮助。我期待听到这方面的想法。

4

3 回答 3

2

对可能降低复杂性的方法的随机思考：

这里真正的限制因素将是您可以如何减少类型集。最明显的方法之一是仅基于对象的键来做某事。数据中有额外键的问题是我们不能只依赖Object.keys( data ).sort().join(",")，我们还必须尝试我们拥有的每个键组合。

// Assuming the "types" list is called "types":
// using underscore.js api
var _ = require('underscore');
var keyMap = _.chain( types ).map(function( typeDef, typeIndex ) {
        // get an index with the definition, in case its 
        return { index: typeIndex, def: typeDef };
    }).groupBy(function( data ) {
        return _.keys( data.def ).sort().join(",");
    }).value();

// empty map needed
keyMap[""] = [];

// assumes sorted key list
function getPossibleMaps( keys ) {
  // if we have a map for this, use it
  if ( keyMap[ keys.join(",") ] ) {
    return keyMap[ keys.join(",") ];
  } else {
    // create a map of possible types by removing every key from the list of keys
    // and then looking for maps that match, cache our result
    return keyMap[ keys.join(",") ] = recursiveMapTest( keys );
  }
}  

function recursiveMapTest( keys ) {
    return _.chain( keys )
      .map(function( key ) {
        return getPossibleMaps( _.without( keys, key ) );
      }).flatten().value();
}

// we must also include "lesser" definitions for each of the key lists we found:
_.each( keyMap, function( results, index ) {
    var keys = index.split(",");
    keyMap[index] = results.concat( recursiveMapTest( keys ) );
});

function getType( data ) {
  function checkType( typeData ) {
    var def = typeData.def;
    return _.every(typeData.def, function( value, key ) {
      // these checks are probably not quite right
      if ( value === null ) {
        return true;
      } else if ( value === Number ) {
        return typeof data[key] === "number" || data instanceof Number;
      } else if ( value === String ) {
        return typeof data[key] === "string" || data instanceof String;
      } else {
        return data[ key ] === value;
      }
    });
  }
  var match = _.find( getPossibleMaps( _.keys( data ).sort() ), checkType );
  return match && match.index;
}

// Retrieve
var clientTypes = [
  { type: 1, name: 'user', password: 'pass' },
  { type: 2, name: 'user', password: 'pass' },
  { type: 2, user_id: 5, action: 'hello' },
  { type: 2, object_id: 5, action: 'hello' },
  { type: 1, name: 'user', password: 'pass', remember_me: true }
];

console.log('Client types:');
for (var i = 0; i < clientTypes.length; i++) {
    var type = clientTypes[i];
    // The type object from the map
    console.log("getType", type, getType(type));
}

jsbin

当然，这只是意味着可能的传入键列表越多，存储“快速”查找表所消耗的内存就越多。

此外，如果一切都有数字类型，您显然可以使用它来加速该子类型中可能的“对象类型”的一大块。

我认为你最好的选择是首先避免需要做任何这些。使用您的对象传递更好的类型提示。

于 2013-02-15T05:05:27.267 回答
0

蓝图将以对象或数组的形式发送。如果您可以将它们作为对象发送，请使用类型 ID 作为键，使用值作为类型对象。在确定类型时，O(1)及时访问该类型的key。

即使您将类型作为数组接收，O(n)传递也允许您将它们存储在内部对象中，并将其用作哈希表以在运行时检索所需的类型信息。

如果您不能依赖类型本身作为键，请为每种类型生成一个唯一键并使用相同的函数进行检索。

var types = [{ // Will refer to this JSON object as type1
    type: 1,
    name: String,
    password: String
},
{ // type2
    type: 2,
    user_id: Number,
    action: String
},
{ // type3
    type: 2,
    object_id: Number,
    action: String
}];

console.log(types);

// Prepare map
var typeMap = {};
for (var i = 0; i < types.length; i++) {
    var type = types[i];
    typeMap[typeKey(type)] = type;
}
console.log(typeMap);

function typeKey(type) {
    var key = '';
    for (var i in type) {
        if (i == 'type') {
            key += type[i].toString() + ':';
        }
        key += ':' + i;
    }
    return key;
}

function getType(type) {
    return typeMap[typeKey(type)];
}

// Retrieve
var clientTypes = [
    { type: 1, name: 'user', password: 'pass' },
    { type: 2, name: 'user', password: 'pass' },
    { type: 2, user_id: 5, action: 'hello' },
    { type: 2, object_id: 5, action: 'hello' }
];
console.log('Client types:');
for (var i = 0; i < clientTypes.length; i++) {
    var type = clientTypes[i];
    // The type object from the map
    console.log(getType(type));
}

如果未找到“客户端”类型的类型，undefined则从 getType 中返回。

http://jsfiddle.net/Kt2sq/1

输出：

Client types:
Object {type: 1, name: function, password: function}
undefined
Object {type: 2, user_id: function, action: function}
Object {type: 2, object_id: function, action: function}
于 2013-02-15T03:30:11.090 回答
0

你可以这样做

var obj1={ type: 1, name: 'user', password: 'pass' };
var obj2={ type: 2, name: 'user', password: 'pass' };

//match JSON keys
var keys1 = Object.keys(obj1);
var keys2 = Object.keys(obj2);
if (JSON.stringify(keys1) === JSON.stringify(keys2))
console.log("matched all keys");

//match JSON value datatypes
for (var key in obj1) {
   if (typeof(obj1[key]) == typeof(obj2[key]))
   console.log(key +' data type matched');
}

//match 'type' field
if (obj1.type == obj2.type)
console.log("woooo total match");

这是时间复杂度：

  1. 关键匹配是 O(n)
  2. 字段数据类型匹配为 O(n)
  3. 类型字段检查是 O(1)

因此，如果订购了 JSON，则总数为 O(n)，否则排序将需要额外的时间。

于 2013-02-15T04:24:16.277 回答