构建关联字符串和数字的可搜索对象的最快方式是什么？

Question

我想在MATLAB中将字符串与数字关联起来。也就是说，我想创建一个对象，它的形式如下：

string: 'abcd', index: 1
string: 'abdd', index: 2
etc.

事实上，我需要能够在提供字符串（例如“ abcd”）时搜索对象，并使其返回相关的（唯一）索引，在此示例中为1。我还需要能够使用索引搜索对象并使其返回关联字符串。新元素将需要相当频繁地添加到此对象中。此对象中将有许多元素（约为500000）。这些字符串本身通常不是“有序”的（即使这样做是否有帮助也不知道）。

问题：在MATLAB中最快的方法是什么？

---

我尝试过的方法：似乎MATLAB中的Map类是相关的；然而，我无法弄清楚如何在两个方向上进行搜索。我的意思可以用Mathworks网站上提供的以下示例来说明：

ticketMap = containers.Map(...
{'2R175', 'B7398', 'A479GY', 'NZ1452'}, ...
{'James Enright', 'Carl Haynes', 'Sarah Latham', ...
 'Bradley Reid'});
ticketMap('2R175') -> returns James Enright

但似乎不支持在另一个方向上进行搜索，也就是说，给定“James Enright”，无法返回“2R175”。我还尝试了Map2代码（http://www.mathworks.com/matlabcentral/fileexchange/40323-map2-enhanced-map-class），但速度非常慢。

- jonem

---

你有没有考虑将字符串放入单元数组中，并使用单元数组的索引作为你的索引？你可以很容易地使用 ismember 在单元数组中进行搜索。 - Cecilia

你尝试过创建两个映射对象A->B和BB->AA吗？其中AA是AA的副本，B是每次插入/删除键-映射对时BB的副本。在这种情况下，您可能需要每个字符串的额外属性，以告诉您需要搜索哪个映射对象。 - Abhinav

当你有大量数据时，尽量使用数据库，通过数据库可以向表中添加、搜索或删除数据，它快速可靠且实现并不困难。(如果您不想使用数据库，则两个映射解决方案也是不错的选择) - Hadi

Answer 1

我想最好的解决方案是建立两个映射表，一个从票号到姓名，另一个从姓名到票号。

示例：

tickets = {'2R175', 'B7398', 'A479GY', 'NZ1452'};
names = {'James Enright', 'Carl Haynes', 'Sarah Latham', 'Bradley Reid'};

ticketMap = containers.Map(tickets, names);

namesMap = containers.Map(names, tickets);
%ticketMap('2R175') -> returns James Enright
%namesMap('James Enright') -> 2R175

创建和管理两个地图可能看起来会浪费内存和计算时间，但考虑到时间复杂度，这是最有效的解决方案。

- Rotem

Answer 2

我想最快的解决方案是一个带有有限错误检查的对象，它保留了一个字符数组的单元格数组和一个相关的索引数组。然后可以使用简单的索引和 strcmp 的组合根据需要进行拉取。

这里有一个这样的对象的快速示例（使用词法闭包，因为我喜欢它们，并且过去看到过更好的性能，但这可能不是现在的情况）。

function store = makeStringMap(strings)

    if (nargin >= 1) && not(isempty(strings))
        if iscellstr(strings) 
            strings = strings(:);
        elseif ischar(strings)
            strings = cellstr(strings);
        else
            error('makeStringStore:wrongInputType',...
                'First input ''strings'' must be either a cellstr or a char array.');
        end
    else
        strings = {};
    end

    nstrings = numel(strings);
    indices  = 1:nstrings;

    store.append = @(string) append(string);
    function [] = append(string)
        if ischar(string)
            string = cellstr(string);
        end
        nstring  = numel(string)                        ;
        strings  = [strings;string]                     ;
        indices  = [indices,(1+nstrings)+(0:(nstring-1))]   ;
        nstrings = indices(end)                         ;
    end

    store.getStringByIndex = @(index) getStringByIndex(index);
    function string = getStringByIndex(index)
        if all(index>0 && index<=nstrings)
            string = strings(index);
        end
    end

    store.getIndexByString = @(string) getIndexByString(string);
    function index = getIndexByString(string)
        if ischar(string)
            string = cellstr(string);
        end
        nstring = numel(string);
        index = zeros(nstring,1);
        for k = 1:nstring
            index = indices(strcmp(strings,string{k}));
        end
    end

    store.getStrings = @() getStrings();
    function out = getStrings()
        out = strings;
    end
end

一个简单的测试运行：

>> s = makeStringMap(char(randi([97,122],5,10)));
>> s.getStrings()
ans = 
    'yheepozpvs'
    'kkdrslqcic'
    'smktndqhjg'
    'nfqikjtsbb'
    'jpfgtdlbem'
>> s.getStringByIndex(2)
ans = 
    'kkdrslqcic'
>> s.getIndexByString(s.getStringByIndex(2))
ans =
     2
>> s.append(char(randi([97,122],3,10)));
>> s.getStringByIndex(7)
ans = 
    'tajrjqmikg'
>> s.getIndexByString(s.getStringByIndex(7))
ans =
     7

我需要说明的是，虽然我经常使用变量string，但这不是新的string类，因为我使用的是R2016a版本，仍经常使用char和cellstr。

- TroyHaskin