Создание | N | x | M | матрица из хэш-таблицы
Представьте, что у меня есть словарь/хэш-таблица из пар строк (ключей) и их соответствующих вероятностей (значений):
import numpy as np
import random
import uuid
# Creating the N vocabulary and M vocabulary
max_word_len = 20
n_vocab_size = random.randint(8000,10000)
m_vocab_size = random.randint(8000,10000)
def random_word():
return str(uuid.uuid4().get_hex().upper()[0:random.randint(1,max_word_len)])
# Generate some random words.
n_vocab = [random_word() for i in range(n_vocab_size)]
m_vocab = [random_word() for i in range(m_vocab_size)]
# Let hallucinate probabilities for each word pair.
hashes = {(n, m): random.random() for n in n_vocab for m in m_vocab}
Хэш-таблица hashes
будет выглядеть примерно так:
{('585F', 'B4867'): 0.7582038699473549,
('69', 'D98B23C5809A'): 0.7341569569849136,
('4D30CB2BF4134', '82ED5FA3A00E4728AC'): 0.9106077161619021,
('DD8F8AFA5CF', 'CB'): 0.4609114677237601,
...
}
Представьте, что это входная хэш-таблица, которую я буду читать из файла CSV, причем первый и второй столбцы являются парами слов (ключей) хеш-таблицы, а третий столбец - вероятностями
Если бы я включил вероятности в какую-то матрицу numpy
, мне пришлось бы делать это из хэш-таблицы:
n_words, m_words = zip(*hashes.keys())
probs = np.array([[hashes[(n, m)] for n in n_vocab] for m in m_vocab])
Есть ли другой способ получить prob
в | N | * | M | матрица из хэш-таблицы без выполнения вложенной петли через m_vocab и n_vocab?
(Примечание: я создаю случайные слова и случайные вероятности здесь, но представьте, что я прочитал хэш-таблицу из файла и прочитал эту структуру хэш-таблицы)
Предположите оба сценария, где:
- Хэш-таблица из файла
csv
(ответ @bunji разрешает это)
- Хэш-таблица взята из маринованного словаря. Или, что хэш-таблица была вычислена каким-то другим способом, прежде чем достичь той части, в которой необходимо преобразовать ее в матрицу.
Важно, чтобы конечная матрица нуждалась в запросе, следующее нежелательно:
$ echo -e 'abc\txyz\t0.9\nefg\txyz\t0.3\nlmn\topq\t\0.23\nabc\tjkl\t0.5\n' > test.txt
$ cat test.txt
abc xyz 0.9
efg xyz 0.3
lmn opq .23
abc jkl 0.5
$ python
Python 2.7.10 (default, Jul 30 2016, 18:31:42)
[GCC 4.2.1 Compatible Apple LLVM 8.0.0 (clang-800.0.34)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import pandas as pd
>>> pt = pd.read_csv('test.txt', index_col=[0,1], header=None, delimiter='\t').unstack().as_matrix()
>>> pt
array([[ 0.5, nan, 0.9],
[ nan, nan, 0.3],
[ nan, nan, nan]])
>>> pd.read_csv('test.txt', index_col=[0,1], header=None, delimiter='\t').unstack()
2
1 jkl opq xyz
0
abc 0.5 NaN 0.9
efg NaN NaN 0.3
lmn NaN NaN NaN
>>> df = pd.read_csv('test.txt', index_col=[0,1], header=None, delimiter='\t').unstack()
>>> df
2
1 jkl opq xyz
0
abc 0.5 NaN 0.9
efg NaN NaN 0.3
lmn NaN NaN NaN
>>> df['abc', 'jkl']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/Library/Python/2.7/site-packages/pandas/core/frame.py", line 2055, in __getitem__
return self._getitem_multilevel(key)
File "/Library/Python/2.7/site-packages/pandas/core/frame.py", line 2099, in _getitem_multilevel
loc = self.columns.get_loc(key)
File "/Library/Python/2.7/site-packages/pandas/indexes/multi.py", line 1617, in get_loc
return self._engine.get_loc(key)
File "pandas/index.pyx", line 139, in pandas.index.IndexEngine.get_loc (pandas/index.c:4160)
File "pandas/index.pyx", line 161, in pandas.index.IndexEngine.get_loc (pandas/index.c:4024)
File "pandas/src/hashtable_class_helper.pxi", line 732, in pandas.hashtable.PyObjectHashTable.get_item (pandas/hashtable.c:13161)
File "pandas/src/hashtable_class_helper.pxi", line 740, in pandas.hashtable.PyObjectHashTable.get_item (pandas/hashtable.c:13115)
KeyError: ('abc', 'jkl')
>>> df['abc']['jkl']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/Library/Python/2.7/site-packages/pandas/core/frame.py", line 2055, in __getitem__
return self._getitem_multilevel(key)
File "/Library/Python/2.7/site-packages/pandas/core/frame.py", line 2099, in _getitem_multilevel
loc = self.columns.get_loc(key)
File "/Library/Python/2.7/site-packages/pandas/indexes/multi.py", line 1597, in get_loc
loc = self._get_level_indexer(key, level=0)
File "/Library/Python/2.7/site-packages/pandas/indexes/multi.py", line 1859, in _get_level_indexer
loc = level_index.get_loc(key)
File "/Library/Python/2.7/site-packages/pandas/indexes/base.py", line 2106, in get_loc
return self._engine.get_loc(self._maybe_cast_indexer(key))
File "pandas/index.pyx", line 139, in pandas.index.IndexEngine.get_loc (pandas/index.c:4160)
File "pandas/index.pyx", line 163, in pandas.index.IndexEngine.get_loc (pandas/index.c:4090)
KeyError: 'abc'
>>> df[0][2]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/Library/Python/2.7/site-packages/pandas/core/frame.py", line 2055, in __getitem__
return self._getitem_multilevel(key)
File "/Library/Python/2.7/site-packages/pandas/core/frame.py", line 2099, in _getitem_multilevel
loc = self.columns.get_loc(key)
File "/Library/Python/2.7/site-packages/pandas/indexes/multi.py", line 1597, in get_loc
loc = self._get_level_indexer(key, level=0)
File "/Library/Python/2.7/site-packages/pandas/indexes/multi.py", line 1859, in _get_level_indexer
loc = level_index.get_loc(key)
File "/Library/Python/2.7/site-packages/pandas/indexes/base.py", line 2106, in get_loc
return self._engine.get_loc(self._maybe_cast_indexer(key))
File "pandas/index.pyx", line 139, in pandas.index.IndexEngine.get_loc (pandas/index.c:4160)
File "pandas/index.pyx", line 161, in pandas.index.IndexEngine.get_loc (pandas/index.c:4024)
File "pandas/src/hashtable_class_helper.pxi", line 404, in pandas.hashtable.Int64HashTable.get_item (pandas/hashtable.c:8141)
File "pandas/src/hashtable_class_helper.pxi", line 410, in pandas.hashtable.Int64HashTable.get_item (pandas/hashtable.c:8085)
KeyError: 0
>>> df[0]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/Library/Python/2.7/site-packages/pandas/core/frame.py", line 2055, in __getitem__
return self._getitem_multilevel(key)
File "/Library/Python/2.7/site-packages/pandas/core/frame.py", line 2099, in _getitem_multilevel
loc = self.columns.get_loc(key)
File "/Library/Python/2.7/site-packages/pandas/indexes/multi.py", line 1597, in get_loc
loc = self._get_level_indexer(key, level=0)
File "/Library/Python/2.7/site-packages/pandas/indexes/multi.py", line 1859, in _get_level_indexer
loc = level_index.get_loc(key)
File "/Library/Python/2.7/site-packages/pandas/indexes/base.py", line 2106, in get_loc
return self._engine.get_loc(self._maybe_cast_indexer(key))
File "pandas/index.pyx", line 139, in pandas.index.IndexEngine.get_loc (pandas/index.c:4160)
File "pandas/index.pyx", line 161, in pandas.index.IndexEngine.get_loc (pandas/index.c:4024)
File "pandas/src/hashtable_class_helper.pxi", line 404, in pandas.hashtable.Int64HashTable.get_item (pandas/hashtable.c:8141)
File "pandas/src/hashtable_class_helper.pxi", line 410, in pandas.hashtable.Int64HashTable.get_item (pandas/hashtable.c:8085)
KeyError: 0
Результирующая матрица /dataframe должна быть запрашиваемой, то есть способна сделать что-то вроде:
probs[('585F', 'B4867')] = 0.7582038699473549
Ответы
Ответ 1
Я не уверен, есть ли способ полностью избежать цикла, но я думаю, что его можно было бы оптимизировать, используя itertools
:
import itertools
nested_loop_iter = itertools.product(n_vocab,m_vocab)
#note that because it iterates over n_vocab first we will need to transpose it at the end
probs = np.fromiter(map(hashes.get, nested_loop_iter),dtype=float)
probs.resize((len(n_vocab),len(m_vocab)))
probs = probs.T
Ответ 2
Если ваша конечная цель состоит в том, чтобы читать ваши данные из CSV файла, было бы легче прочитать файл напрямую, используя pandas.
import pandas as pd
df = pd.read_csv('coocurence_data.csv', index_col=[0,1], header=None).unstack()
probs = df.as_matrix()
это считывает ваши данные из csv, делает первые два столбца в multi-index, который соответствует вашим двум наборам слов. Затем он разбивает мультииндекс так, что у вас есть один набор слов в качестве меток столбцов, а другой - как индексные метки. Это дает вам ваш | N | * | M | которая затем может быть преобразована в массив numpy с функцией .as_matrix()
.
Это не решит ваш вопрос об изменении вашего словаря {(n,m):prob}
в массив numpy, но, учитывая ваши намерения, это позволит вам избежать необходимости создания этого словаря в целом.
Кроме того, если вы все равно будете читать в csv, чтение его с помощью pandas в первую очередь будет быстрее, чем использование встроенного модуля csv
в любом случае: см. эти контрольные тесты здесь
ИЗМЕНИТЬ
Чтобы запросить определенное значение в вашем DataFrame на основе ярлыков строк и столбцов, df.loc
:
df.loc['xyz', 'abc']
где 'xyz'
- ваше слово в ярлыке строки, а 'abc'
- это метка столбца. Также проверьте df.ix
и df.iloc
для других способов запроса определенных ячеек в вашем DataFrame.
Ответ 3
[короткое расширение ответа dr-xorile]
Большинство решений выглядят хорошо для меня. Зависит немного, если вам нужна скорость или удобство.
Я согласен, что у вас в основном матрица в разреженном формате. Возможно, вы захотите посмотреть https://docs.scipy.org/doc/scipy-0.18.1/reference/sparse.html
Проблема только в том, что для матриц нужны целые индексы. Так что пока ваши хэши достаточно малы, чтобы быстро выражаться как np.int64
, которые должны работать. И разреженный формат должен позволять доступ к $O (1) $ко всем элементам.
(Извините за краткость!)
грубая схема
Это потенциально может быть быстрым, но вроде хаки.
-
получить данные в разреженном представлении. Я думаю, вы должны выбрать coo_matrix
, чтобы просто удерживать 2D-карту хэша.
а. загрузите CSV с помощью numpy.fromtxt
и используйте, например, datatype ['>u8', '>u8', np.float32]
для обработки хэшей в виде строковых представлений целых чисел без знака 8байт. Если это не работает, вы можете загружать строки и использовать numpy для его преобразования. Наконец, у вас есть три таблицы размера N * M, как и ваша хеш-таблица, и используйте их с видимым разреженным матричным представлением по вашему выбору.
б. если у вас уже есть объект в памяти, вы можете напрямую использовать разреженный конструктор.
-
Чтобы получить доступ, вам нужно снова проанализировать свои строки
prob = matrix[np.fromstring(key1, dtype='>u8'), np.fromstring(key2, dtype='>u8')]
Ответ 4
Кажется, немного неэффективно пройти через все пространство n_vocab x m_vocab для разреженной матрицы! Вы можете перебрать таблицу исходных хэшей. Было бы хорошо сначала узнать пару вещей:
-
Знаете ли вы размер n_vocab и m_vocab upfront? Или ты собираешься понять это, когда строишь его?
-
Знаете ли вы, есть ли какие-либо повторения в вашей хеш-таблице, и если да, то как вы справитесь с этим? Похоже, что хэш - это словарь, и в этом случае, очевидно, ключи уникальны. На практике это, вероятно, означает, что вы переписываете каждый раз, и поэтому последнее значение будет стоять.
В любом случае, здесь сравнение двух опций:
from collections import defaultdict
import numpy as np
hashes = defaultdict(float,{('585F', 'B4867'): 0.7582038699473549,
('69', 'D98B23C5809A'): 0.7341569569849136,
('4D30CB2BF4134', '82ED5FA3A00E4728AC'): 0.9106077161619021,
('DD8F8AFA5CF', 'CB'): 0.4609114677237601})
#Double loop approach
n_vocab, m_vocab = zip(*hashes.keys())
probs1 = np.array([[hashes[(n, m)] for n in n_vocab] for m in m_vocab])
#Loop through the hash approach
n_hash = dict() #Create a hash table to find the correct row number
for i,n in enumerate(n_vocab):
n_hash[n] = i
m_hash = dict() #Create a hash table to find the correct col number
for i,m in enumerate(m_vocab):
m_hash[m] = i
probs2 = np.zeros((len(n_vocab),len(m_vocab)))
for (n,m) in hashes: #Loop through the hashes and put the values into the probs table
probs2[n_hash[n],m_hash[m]] = hashes[(n,m)]
Вывод проб 1 и probs2, конечно же, тот же:
>>> probs1
array([[ 0.73415696, 0. , 0. , 0. ],
[ 0. , 0.46091147, 0. , 0. ],
[ 0. , 0. , 0.75820387, 0. ],
[ 0. , 0. , 0. , 0.91060772]])
>>> probs2
array([[ 0.73415696, 0. , 0. , 0. ],
[ 0. , 0.46091147, 0. , 0. ],
[ 0. , 0. , 0.75820387, 0. ],
[ 0. , 0. , 0. , 0.91060772]])
И, конечно, ваш код для probs1 очень короткий. Однако размер петель существенно отличается, и это может иметь большое значение для времени выполнения
Ответ 5
Я попытался уменьшить размер выборки, чтобы быстро сравнить разные коды. Я кодировал метод dataframe, который все еще может использоваться для цикла в функции pandas и по сравнению с исходным кодом и кодом itertools, предоставленным Tadhg McDonald-Jensen. Самый быстрый код - itertools.
In [3]: %timeit itertool(hashes,n_vocab,m_vocab)
1000 loops, best of 3: 1.12 ms per loop
In [4]: %timeit baseline(hashes,n_vocab,m_vocab)
100 loops, best of 3: 3.23 ms per loop
In [5]: %timeit dataframeMethod(hashes,n_vocab,m_vocab)
100 loops, best of 3: 5.49 ms per loop
Это код, который я использовал для сравнения.
import numpy as np
import random
import uuid
import pandas as pd
import itertools
# Creating the N vocabulary and M vocabulary
max_word_len = 20
n_vocab_size = random.randint(80,100)
m_vocab_size = random.randint(80,100)
def random_word():
return str(uuid.uuid4().get_hex().upper()[0:random.randint(1,max_word_len)])
# Generate some random words.
n_vocab = [random_word() for i in range(n_vocab_size)]
m_vocab = [random_word() for i in range(m_vocab_size)]
# Let hallucinate probabilities for each word pair.
hashes = {(n, m): random.random() for n in n_vocab for m in m_vocab}
def baseline(hashes,n_vocab,m_vocab):
n_words, m_words = zip(*hashes.keys())
probs = np.array([[hashes[(n, m)] for n in n_vocab] for m in m_vocab])
return probs
def itertool(hashes,n_vocab,m_vocab):
nested_loop_iter = itertools.product(n_vocab,m_vocab)
#note that because it iterates over n_vocab first we will need to transpose it at the end
probs = np.fromiter(map(hashes.get, nested_loop_iter),dtype=float)
probs.resize((len(n_vocab),len(m_vocab)))
return probs.T
def dataframeMethod(hashes,n_vocab,m_vocab):
# build dataframe from hashes
id1 = pd.MultiIndex.from_tuples(hashes.keys())
df=pd.DataFrame(hashes.values(),index=id1)
# make dataframe with one index and one column
df2=df.unstack(level=0)
df2.columns = df2.columns.levels[1]
return df2.loc[m_vocab,n_vocab].values