objective-c - NSMutableDictionary 用于巨大的 float 数据集

标签 objective-c c performance hashmap nsmutabledictionary

我有一些代码可以将一个大的(许多 GB 的)XML 文件转换成另一种格式。

除其他事项外,我需要在哈希表中存储一或两千兆字节的 float (每个条目两个 float ),并使用一个 int 作为值的键。

目前,我正在使用 NSMutableDictionary 和一个包含两个 float 的自定义类:

// create the dictionary
NSMutableDictionary *points = [[NSMutableDictionary alloc] init];

// add an entry (the data is read from an XML file using libxml)
int pointId = 213453;
float x = 42.313554; 
float y = -21.135213; 

MyPoint *point = [[MyPoint alloc] initWithX:x Y:y];
[points setObject:point forKey:[NSNumber numberWithInt:pointId]];
[point release];

// retrieve an entry (this happens later on while parsing the same XML file)
int pointId = 213453;
float x;
float y;
MyPoint *point = [points objectForKey:[NSNumber numberWithInt:pointId]];
x = point.x;
y = point.y;

这个数据集和我现在处理的 XML 文件一起消耗了大约 800MB 的 RAM,而且执行需要相当长的时间。我想要更好的性能,但更重要的是我需要降低内存消耗,这样我才能处理更大的 XML 文件。

objc_msg_send 就在代码概要中,- [NSNumber numberWithInt:] 也是,我确信我可以通过完全避免对象来降低内存使用量,但我不太了解 C 编程(这个项目肯定在教我!)。

如何用高效的 C 数据结构替换 NSMuableDictionaryNSNumber MyPoint?没有任何第三方库依赖?

我还希望能够将此数据结构写入磁盘上的文件,这样我就可以处理不完全适合内存的数据集,但我可能没有这种能力也能生活。

(对于那些不熟悉 Objective-C 的人来说,NSMutableDictionary 类只能存储 Obj-C 对象,它的键也必须是对象。NSNumber 和 MyPoint 是哑容器类,允许 NSMutableDictionary 与 float 一起工作和 int 值。)

编辑:

我已经尝试使用 CFMutableDictionary 来存储结构,根据 apple's sample code .当字典为空时,它表现很好。但是随着字典的增长,它变得越来越慢。大约 25% 通过解析文件(字典中的约 400 万个项目)它开始突然出现,比文件中的早期慢两个数量级。

NSMutableDictionary 没有同样的性能问题。 Instruments 显示了很多应用散列和比较字典键的事件(下面的 intEqual() 方法)。比较一个 int 是很快的,所以如此频繁地执行它是非常错误的。

这是我创建字典的代码:

typedef struct {
  float lat;
  float lon;
} AGPrimitiveCoord;

void agPrimitveCoordRelease(CFAllocatorRef allocator, const void *ptr) {
    CFAllocatorDeallocate(allocator, (AGPrimitiveCoord *)ptr);
}

Boolean agPrimitveCoordEqual(const void *ptr1, const void *ptr2) {
    AGPrimitiveCoord *p1 = (AGPrimitiveCoord *)ptr1;
    AGPrimitiveCoord *p2 = (AGPrimitiveCoord *)ptr2;

    return (fabsf(p1->lat - p2->lat) < 0.0000001 && fabsf(p1->lon - p2->lon) < 0.0000001);

}

Boolean intEqual(const void *ptr1, const void *ptr2) {
    return (int)ptr1 == (int)ptr2;
}

CFHashCode intHash(const void *ptr) {
  return (CFHashCode)((int)ptr);
}

// init storage dictionary
CFDictionaryKeyCallBacks intKeyCallBacks = {0, NULL, NULL, NULL, intEqual, intHash};
CFDictionaryValueCallBacks agPrimitveCoordValueCallBacks = {0, NULL /*agPrimitveCoordRetain*/, agPrimitveCoordRelease, NULL, agPrimitveCoordEqual};
temporaryNodeStore = CFDictionaryCreateMutable(NULL, 0, &intKeyCallBacks, &agPrimitveCoordValueCallBacks);

// add an item to the dictionary
- (void)parserRecordNode:(int)nodeId lat:(float)lat lon:(float)lon
{
  AGPrimitiveCoord *coordPtr = (AGPrimitiveCoord *)CFAllocatorAllocate(NULL, sizeof(AGPrimitiveCoord), 0);
  coordPtr->lat = lat;
  coordPtr->lon = lon;

  CFDictionarySetValue(temporaryNodeStore, (void *)nodeId, coordPtr);
}

编辑 2:

性能问题是由于 Apple 示例代码中几乎无用的哈希实现。我通过使用它获得了性能提升:

// hash algorithm from http://burtleburtle.net/bob/hash/integer.html
uint32_t a = abs((int)ptr);
a = (a+0x7ed55d16) + (a<<12);
a = (a^0xc761c23c) ^ (a>>19);
a = (a+0x165667b1) + (a<<5);
a = (a+0xd3a2646c) ^ (a<<9);
a = (a+0xfd7046c5) + (a<<3);
a = (a^0xb55a4f09) ^ (a>>16);

最佳答案

如果你想要类似 NSMutableDictionary 的行为但使用 malloc 内存,你可以下拉到 CFDictionary (或者在您的情况下, CFMutableDictionary )。它实际上是 NSMutableDictionary 的基础,但它允许一些自定义,即您可以告诉它您没有存储对象。当你调用 CFDictionaryCreateMutable() 时,你给它一个结构来描述你传递给它的值类型(它包含告诉它如何保留、释放、描述、散列和比较你的值的指针).所以如果你想使用一个包含两个 float 的结构,并且你很高兴为每个结构使用 malloc 内存,你可以 malloc 你的结构,填充它,然后把它交给 CFDictionary,然后然后你可以编写回调函数,使它们与你的特定结构一起工作。您可以使用 CFDictionary 的键和对象的唯一限制是它们需要放在 void * 中。

关于objective-c - NSMutableDictionary 用于巨大的 float 数据集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8936428/

相关文章:

c - 将 GSS-SPNEGO 与 gss_krb5_import_cred 结合使用

c++ - 什么方法可以创建 16 字节校验和

java Tigase 性能

ios - 动画后 UITableViewCell 位置关闭

objective-c - 最佳实践访问器 : @property @synthetise

ios - 由于位置管理器的原因,展开转场后发生崩溃

mysql - 在本地主机上使用 OpenSSL 连接到 MySql 数据库

ios - Firebase 持久化,清除 Firebase 缓存

c - C中类型转换和按位运算的结果取决于顺序

java - 似乎在等待的线程的高 CPU 使用率