相同数据的多种查找结构：内存重复？ [英] Multiple lookup structures for same data: Memory duplication?
问题描述
在许多语言中，每个人只需在堆上分配一次。每个数据结构都会包含指向该内存的指针。因此，每次添加新的查找方式时，都不会分配一组新人。
在Haskell中如何？当不同的数据结构需要索引相同的数据时，有什么办法可以避免内存重复？解析方案
我确信有更深入的，对这个问题更有见识的回答，但是暂时......
因为在纯函数式编程语言中数据是不可变的，所以不需要
作为一个非常肮脏的例子，我启动了ghci解释器：
Prelude>让x =全部复制10000'm'（== x）$ replicate 10000 x
True
（1.61 secs，0 bytes）
我承认这些统计信息是不可靠的，但是它并没有为10000个字符长的列表的所有10000个副本分配内存。
$ b $ h
避免内存重复的方法是在
（a）中使用haskell
（b）避免毫无意义地重建您的数据。
我该如何无意义地重建我的数据？
一个非常简单而毫无意义的例子：
pointlessly_reconstruct_list :: [a] - > ; [a]
pointlessly_reconstruct_list [] = []
pointlessly_reconstruct_list（x：xs）= x：xs
这种事情会导致列表结构的重复。
你有没有一点没有意义但仍然简单的例子有趣的是，如果你做 xs ++ ys ，你基本上会重建 xs ，以便在它的末尾放置 ys （替换 [] ） ，因此 xs 的列表结构几乎是批量复制的。然而，没有必要来复制实际的数据，当然只需要一个 ys 的副本。
Suppose I have data on a bunch of people, and I want to be able to look them up in different ways. Maybe there's some kind of data structure (like a binary tree) that facilitates lookup by name. And maybe there's another (like a list) that's by order of creation. And perhaps many more.
In many languages, you would have each person allocated exactly once on the heap. Each data structure would contain pointers to that memory. Thus, you're not allocating a new set of people every time you add a new way to look them up.
How about in Haskell? Is there any way to avoid memory duplication when different data structures need to index the same data?
I feel sure there's a deeper, more knowledgeable answer to this question, but for the time being...
Since in a pure functional programming language data is immutable, there's no need to do anything other than copy the pointer instead of copying its target.
As a quick and very dirty example, I fired up the ghci interpreter:
Prelude> let x = replicate 10000 'm' in all (==x) $ replicate 10000 x
True
(1.61 secs, 0 bytes)
I admit that these stats are unreliable, but what it's not doing is allocating memory for all 10000 copies of a list 10000 characters long.
Summary:
The way to avoid memory duplication is to
(a) use haskell
(b) avoid pointlessly reconstructing your data.
How can I pointlessly reconstruct my data?
A very simple and pointless example:
pointlessly_reconstruct_list :: [a] -> [a]
pointlessly_reconstruct_list [] = []
pointlessly_reconstruct_list (x:xs) = x:xs
This kind of thing causes a duplicate of the list structure.
Have you got any examples that are a little less pointless but still simple?
Interestingly, if you do xs ++ ys you essentially reconstruct xs in order to place ys at the end of it (replacing []), so the list structure of xs is nearly copied wholesale. However, there's no need to replicate the actual data, and there certainly only needs to be one copy of ys.
这篇关于相同数据的多种查找结构：内存重复？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
