Можно ли это назвать хеш-таблицей. Если нет то почему ?

#data_structures #структуры_данных #алгоритм #хеширование #cpp

Почитал кормена и написал хеш-таблицу на основе сцепления элементов. Можно ли это
назвать хеш-таблицей и если нет то почему, какие ошибки есть логические ?
node.hpp
#ifndef NODE_HPP
#define NODE_HPP

template 
class list;

template 
class node
{
    private:
        friend class list;

    private:
        node* m_next;
        node* m_prev;
        T m_data;

    public:
        node() :  m_next(0)
                , m_prev(0)
                , m_data(0) {}

        explicit node(T d) :  m_next(0)
                            , m_prev(0)
                            , m_data(d) {}
        T get_data()
        {
            return m_data;
        }
};

#endif // NODE_HPP

list.hpp
#ifndef LIST_HPP
#define LIST_HPP

#include 
#include 

#include "node.hpp"

template 
class list
{
    private:
        node* m_head;
        node* m_tail;
        unsigned m_size;

    public:
        list() :   m_size(0) 
                 , m_head(0)
                 , m_tail(0){}

        node* get_new_node(T d) const;
        node* find(T data) const;
        void insert_at_front(T data);
        void insert_at_back(T data);
        void delete_at_front();
        void delete_at_back();
        bool is_empty() const;
        void print() const;
        node* get_begin() const
        {
            return m_head;
        }
        node* get_end() const
        {
            return m_tail;
        }
        unsigned get_size() const
        {
            return m_size;
        }
};

template 
node* list::get_new_node(T data) const 
{
    node* n = new node(data);
    assert(n != 0);
    return n;
}

template 
bool list::is_empty() const
{
    if(m_head == 0)
    {
        return true;
    }
    return false;
}

template 
void list::print() const 
{
    if(is_empty())
    {
        return;
    }
    node* t = m_head;
    while(t != 0)
    {
        std::cout << t->m_data << " ";
        t = t->m_next;
    }
}

template 
node* list::find(T data) const
{
    if(is_empty())
    {
        return 0;
    }
    node* t = m_head;
    while(t != 0 && t->m_data != data)
    {
        t = t->m_next;
    }
    return t;
}

template 
void list::insert_at_front(T data)
{
    node* n = get_new_node(data);
    if(m_head == 0)
    {
        m_head = m_tail = n;
        n->m_next = n->m_prev = 0;
        ++m_size;
    }
    else
    {
        n->m_next = m_head;
        if(m_head != 0)
        {
            m_head->m_prev = n;
        }
        m_head = n;
        n->m_prev = 0;
        ++m_size;
    }
}

template 
void list::insert_at_back(T data)
{
    node* n = get_new_node(data);
    if(m_tail == 0)
    {
        m_head = m_tail = n;
        n->m_next = n->m_prev = 0;
        ++m_size;
    }
    else
    {
        m_tail->m_next = n;
        n->m_prev = m_tail;
        m_tail = n;
        ++m_size;
    }

}

template 
void list::delete_at_front()
{
    if(is_empty())
    {
        return;
    }
    else
    {
        node* t = m_head->m_next;
        t->m_prev = 0;
        delete m_head;
        m_head = t;
        --m_size;
    }
}

template 
void list::delete_at_back()
{
    if(is_empty())
    {
        return;
    }
    else
    {
        node* t = m_tail->m_prev;
        t->m_next = 0;
        delete m_tail;
        m_tail = t;
        --m_size;
    }
}

#endif // LIST_HPP

hash_table.hpp
#ifndef HASH_TABLE_HPP
#define HASH_TABLE_HPP

#include "list.hpp"

template 
class hash_table
{
    private:
        list** m_table;
        unsigned m_size;

    private:
        int get_hash(int key);

    public:
        explicit hash_table(unsigned);
        T find(const T&, const T&); 
        void insert(const T&, unsigned);
        void remove(const T&);
};

template 
hash_table::hash_table(unsigned size)
{
    m_size = size;
    m_table = new list*[m_size];
    for(int i = 0; i < m_size; ++i)
    {
        m_table[i] = new list();
    }
}

template 
int hash_table::get_hash(int key)
{
    return (key % m_size);
}

template 
T hash_table::find(const T& d, const T& i)
{
    int h = get_hash(i);
    node* n = m_table[h]->find(d);
    assert(n != 0);
    return n->get_data();
}

template 
void hash_table::insert(const T& d, unsigned key)
{
    unsigned h = get_hash(key);
    m_table[h]->insert_at_front(d);
}

#endif // HASH_TABLE_HPP

Поправил код find(...)
template 
T hash_table::find(const T& i)
{
    int h = get_hash(i);
    if(m_table[h]->get_begin() != 0)
    {
        return m_table[h]->get_begin()->get_data();
    }
    return 0;
}

но так получается что функция всегда возвращает только голову списка а если есть
коллизия то этот случай не учитывается ... ?    

Ответы

Ответ 1

Есть несколько замечаний по реализации:




Непонятна сигнатура find(T, T). Почему не find(Key)?


Непонятно ваше разделение  для элементов хэш-таблицы. То есть, сигнатуры
методов должны выглядеть как insert(Key, Value) / find(Key) / remove(Key), либо как
insert(Value) / find(Value) / remove(Value) для случая, когда в хэш-таблице хранятся
не пары ключ-значение, а сами значения. Других вариантов нет.


Не предложена имплементация remove(T). Вместо траты времени на реализацию своего
std::list, лучше бы уж написали метод удаления элементов из хэш-таблицы.


Крайне странное решение, в котором вызов функции find() coredump'ится в случае отсутствующего
в хэш-таблице значения.


Вообще, предложенный код, за исключением последних пятнадцати строчек, не имеет к
хэш-таблицам никакого отношения, а просто предлагает какой-то неочевидный способ реализации
аналога std::list. Решение с наследованием node ← list, кстати, кажется очень
странным.




А так, ну да, обычная хэш-таблица с chaining'ом для резолвинга коллизий.


Ответ 2

Похоже, что да, это может быть хэш таблицей. Для начала читаем определение с википедии: 
Хеш-табли́ца — это структура данных, реализующая интерфейс ассоциативного массива,
а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию
добавления новой пары, операцию поиска и операцию удаления пары по ключу.

Все эти три операции я  вижу. Правда было бы  не плохо перегрузить operator [] (что
бы реализовать интерфейс "массива").
Меня  только смущает порядок параметров в функции вставки. Я думаю, ключ должен идти
первым.
Обязательно напишите тестовые примеры и проверьте, что бы Ваша таблица работала как
нужно.

Большие объемы данных

#data_structures #sql #mysql #база_данных

Необходимо предоставить пользователям доступ к записям некоторой таблицы. 
В таблице имеется 11 столбцов, каждый из которых является некоторым идентификатором
записи в другой таблице. 
В день кол-во записей в данной таблице увеличивается на 30 миллионов записей.
Пользователям необходимо знать кол-во событий, подходящих под заданный ими набор
фильтров.
Скорость выполнения запроса допустима в пределах 1 - 3 секунд.
Всего около 5 пользователей.
Как оптимизировать работу таблицы?
Возможно, необходимо построить правильные индексы, но это все же не спасает. 
Возможно, стоит просчитывать кол-во записей, которые попадают под каждый из всевозможных
фильтров. Но тогда кол-во записей возрастет во много раз.
Возможно, есть другие варианты?    

Ответы

Ответ 1

30 миллионов - это много. Даже на самых хороших индексах это будет медленно. В этих
случаях используют предвычисления. 
К примеру, собирал статистику каждый час в отдельную таблицу(таблицы). В этом случае
можно будет очень быстро с дополнительной таблицы получить данные, а остаток за последний
час выбрать с основной таблицы.
Но делать постоянные выборки - это неверно. Особенно в высоконагруженных проектах.
В этих случаях берут какой нибудь MQ (message Queue, например, RabbitMQ)  и данные
льются в него одним потоком. А другой сервер вычитывает и обновляет счетчики. В этом
случае можно будет сделать даже realtime отображение статистики. Если счетчиков много,
то серверов обработки может быть много.
Понятно, что на все фильтры заранее не наготовишь счетчиков, но если подойти грамотно,
то большинство задач можно покрыть. А вот редкие специфические запросы можно уже и
с базы аккуратно вытянуть (я думаю, пользователи с этим смирятся).


Ответ 2

Если Вас не спасает построение правильных индексов, Вам надо менять архитектуру базы
данных. Возможно, так же, имеет смысл генерировать таблицы соответствующие результату
работы фильтров, и делать это или "в ночь" или "на лету", при добавлении новых записей.

Как создать гибкую схему таблиц для хранения сообщений из разных чатов?

#mysql #data_structures

Помогите пожалуйста разобраться в следующей ситуации:

Есть два вида API где хранятся истории сообщений, это Zopim и Chat2Desc(импортировать
в Postman) . Пока эти два но могут потом и другие появится.

И моя ДБ с таблицей users:

Table users
id , email, phone, ...


В Zopim пользователи идентифицируются через email, a в Chat2Desc через телефон. Для
меня эти два поля важны, какой бы чат  не был и сколько бы их не было.

То есть если я получаю емайл либо телефон пользователя в сообщениях, то делаю запрос
в свою базу (table users) для идентифицирования своего пользователя.

Да и в принципе даже структура чатов не важна, я данные как нибудь да выберу.А вот
как их правильно сохранить , да так чтоб у меня была одна структура для всех .

И вот что я придумал:


Разъяснение:

Таблица chats (Данные для чата) :


client_id   - указывает на id таблицы chat_clients
duration    - длительность чата
system_type - хранит имя чата (Zopim, Chat2Desc, ... )
created_at  - дата создания 


Таблица chat_clients (сведений об пользователей которые были в чате):


assigned_data - те инициалы под которыми пользователи были в чате
is_agent      - (0 | 1): 1 => мой пользователь, 0 => не мой
users_id      - id пользователя. Содержит либо id из таблицы users либо пустой.
bean_module   - неважно (сведение о моём пользователе)
unique_col    - Тут будет либо email (из Zopim) либо телефон (из Chat2Desc, Либо
думаю хранить id таблицы users).Будет гарантировать уникальность значений.


Связка users_id + unique_col уникальна (UNIQUE KEY user_id_unique_col_UQ (user_id,unique_col))

Таблица chat_messages:


text      - текст сообщения.
client_id - указывает на id таблицы chat_clients
chat_id   - указывает на id таблицы chats
file_id   - указывает на id таблицы chat_files
transport - значение будет для Chat2Desc (Viber, WhatsApp ,...), для Zopim ,чтоб
не пустовал , Zopim


Таблица chat_files Сведения о переданных файлах в чате.Aналогичных таблиц может быть
может нет для хранения дополнительной инфы.


  Доп инфо: В дальнейшем собираюсь для каждого пользователя выводит
  историю сообщений.


Вопрос:
Как создать гибкую схему таблиц для хранения сообщений из разных чатов ?

Заранее благодарю.
    

Ответы

Ответ 1

Любые проблемы по созданию БД нужно разбивать на две части:


Нужно выделить то, что уже есть. Выделить данность, реальность. То, что вы не можете
изменить. То есть, выделить структуру внешних данных.
Нужно выделить то, что вы хотите получить. Желаемый вид и форма.


У вас в структуре всё в одной куче. И материальное представление, и логический вид.
Вам нужно выделить отдельные структуры под хранения данных из каждой отдельной системы
чатов, которые вы поддерживаете. Так как структуры от­личаются ключами привязки к пользователям,
это должны быть разные структуры. Нет, ко­не­чно, можно всё сделать в одной таблице,
но тут вы ничего не приобретёте, но очень про­иг­ра­ете в сложности структуры. Если
вам нужно делать уникальный ключ по двум ко­лонкам, то вы что-то делаете не так.

Затем нужно выделить то, что вы хотите получить. Значить вам нужна какая-то таблица
свя­зки чатов и пользователей, и таблицы связки чатов в основной таблице и чатов в
мате­риаль­ных таблицах. Если нужно хранить сообщения в каждом чате для быстрого доступа,
то лучше будет это сделать явно, в отдельной таблице, не связанной с материальным пред­став­лением.
Так сообщения будут храниться два раза, но вы не будете связаны материальным пред­став­лением
после импорта сообщений, и ваш код получения данных из БД будет много проще и надёжней.

В современном мире нет смысла пытаться оптимизировать число таблиц в БД: если у вас
их будет десять или сотня, само по себе это нисколько не повлияет на скорость работы
с БД. Другое дело что сложная для понимания структура БД будет отнимать ваше время
и на первоначальную разработку, и на дальнейшую поддержку. Если траты вашего времени
можно избежать, то это следует сделать.

Сама сложная структура БД может представлять и сложность при масштабировании. Например,
шардинг и уникальные индексы идут по разные стороны улицы: вы не можете использовать
шардинг одновременно с уникальными индексами. То же можно сказать про скорость вставки
записей: уникальные индексы ей не помогают.

разница list и array

#массивы #list #memory #data_structures

Можно ли говорить об общих различиях между типами данных list и array независимо
от языка программирования? В частности, по способу доступа к элементам?
В Python что является "истинным" списком -- list или tuple?
Какая из этих структур требует больше памяти и при каких условиях?

    

Ответы

Ответ 1

Строго говоря, связный список и массив - это различные структуры данных, которые
не привязаны к конкретному языку программирования.

Массив

Массив - это совокупность однотипных данных, расположенных непрерывно в памяти. Доступ
к элементу осуществляется по индексу за O(1) - мы обращаемся непосредственно к нужному
участку памяти.

Связанный список

Доступ к элементу в связном списке в среднем занимает O(N) путем перебора элементов
в поисках нужного. Способы доступа к элементам отличаются по реализации и от языка
программирования. Например, на Java в стандартном классе LinkedList в зависимости от
ситуации проход элементов может начинаться как с начала, так и с конца списка. И поиск
элемента может осуществляться как по индексу, так и по сравнению элементов.

Связный список требует больших расходов памяти при прочих равных условиях за счет
хранения указателей на следующий/предыдущий элементы и особенностей внутренней реализации.

Что касается Python: согласно документации:


  Internally, a list is represented as an array; the largest costs come from growing
beyond the current allocation size (because everything must move), or from inserting
or deleting somewhere near the beginning (because everything after that must move).


Как видим, внутренне list представляет собой массив, для tuple - аналогично.


Ответ 2

Нельзя сказать что есть какая-то разница независимо от языка программирования, так
как автор каждого языка может определить эти слова так, как хочет.

Тем не менее, как мне кажется, разница между коллекциями список (list), массив (array)
и кортеж (tuple) заключается в следующих характеристиках:


Фиксированность размера - если размер коллекции фиксирован, то нельзя добавить или
удалить элементы динамическим образом:

int[] x = new int[2];
x[0] = 50;
x[1] = 45;
x[2] = 40; // скорее всего тут будет ошибка или неопределённое поведение


А если размер не фиксирован, можно добавить элементы динамическим образом:

List x = new List();
x.add(50);
x.add(45);
x.add(40);

Изменчивость данных - если коллекция изменяемая, то можно изменить данные после создания,
а если неизменяемая, то нет.


Конкретная разница:


Размер фиксирован, изменяемый: массив (array)
Размер фиксирован, неизменяемый: кортеж (tuple)
Размер не фиксирован, изменяемый: список (list)
Размер не фиксирован, неизменяемый: неизменяемый список (immutable list)


По поводу памяти и скорости: это точно зависит от языка и конкретного структура.
Например, сложность доступа к элементу по индексу в списке может быть O(1) (например
C# List), O(log(n)) (например куча), или O(n) (например связный список).

Мертвы ли списки? C

#c #память #структуры_данных #data_structures

Изучаю структуры данных и алгоритмы, работал с чужими исходниками и не раз видел
реализацию "бесконечного буфера" с помощью realloc, всегда реализовывал свой вариант
поблочным выделением, и оставлением указателя на следующий блок.

struct Node{
    void *data;
    struct Node *next;
}


Появились следующие вопросы:


Как затратней, realloc или моя реализация?
Почему создатель связного списка его не использует?
Как работает класс vector в C++?
Почему в C++ есть аналог malloc, calloc и free (new, new [], delete), но нет аналога
realloc?


Пожалуйста приведите как реализовываете вы, как лучше, почему.

UPD


Что затратней выделять память или копировать один участок в другой (уже выделенный),
на сколько затратней?

    

Ответы

Ответ 1

Архитектура современных компьютеров такова, что массивы (и любые структуры данных,
основанные на них) оказываются в большинстве случаев быстрее, чем связные списки.

Кеш

Все дело в кеше. В одной линии кеша располагается сразу несколько элементов массива.
Следовательно, при доступе к ним процессор не тратит много времени. А элементы связного
списка с высокой долей вероятности не попадут в одну линию кеша. Следовательно, при
обращении к очередному элементу будет промах и процессору придётся обращаться к основной
памяти.

Память

Английское название - RAM (random access memory) - память со случайным доступом -
давным-давно стало неправильным обозначением этого типа памяти. На самом деле она давно
является блочной. Кстати, русское ОЗУ (оперативное запоминающее устройство), не несёт
в своём определении такого недостатка.

Современная память устроена так, что пишет/читает данные большими порциями. Подготовка
к чтению и записи (латентность) занимает много времени. Зато потом данные выстреливаются
очень быстро. Нетрудно понять, что последовательно размещённый массив будет читаться
и писаться намного быстрее, чем связный список, элементы которого размещены в разных
банках памяти.


Ответ 2

Как затратней, realloc или моя реализация?


Для чего? С точки зрения памяти, локальности, поиска, сортировки...? Как будете выделять
память - каждый раз по одному элементу или сразу раза в 2 больший буфер и поддерживать
его емкость/заполненность? Вопрос поставлен некорректно...


Почему создатель связного списка его не использует?


А "создатель" - это кто? без этого непонятно, использует ли он его или нет...

Update С тем же успехом, что считать Блоха создателем связанного списка, можно считать
собравшего из разного железа в гараже велосипед слесаря дядю Васю - создателем велосипеда.
Но дяде Васе просто некуда и незачем на нем ездить. Как и у Блоха, вероятно, нет задач,
для которых связанный список более подходящ, чем массив...


Как работает класс vector в C++?


Поддерживая буфер, увеличиваемый по заполнении в некоторое количество раз - например,
в два, так что обычно в нем есть достаточно пустого места для новых элементов. Когда
заполняется - выделяется новый буфер удвоенного размера, куда перекопируется содержимое
старого. Так что в результате амортизированное количество копирований - O(1), а все
данные хранятся в одном блоке памяти.


Почему в C++ есть аналог malloc, calloc и free (new, new[], delete), но нет аналога
realloc?


Ну, я бы не говорил, что это аналоги, уж тем более что new[] - аналог calloc. Эти
"аналоги" вызывают конструкторы и деструкторы, а при realloc это, скажем так, задача,
которую непросто решить для нетривиальных типов. Это совсем не так просто, как в С
-  перебросить память с одного места в другое...


Ответ 3

Как затратней, realloc или моя реализация?


Выделение памяти- это дорогостоящий процесс.
Именно по этому память любят выделять с запасом.

Более того, происходит копирования всего старого блока памяти на новый участок памяти
нового размера(если размер увеличивается).

Поэтому реализация без постоянного дерганья realloc более производительна.


  Как работает класс vector в C++?
  
  Типичная реализация вектора — это указатель на динамический массив.
  Размер вектора — это фактическое число элементов, а объём — количество
  используемой им памяти.
  
  Если при вставке в вектор новых элементов, его размер становится
  больше его объёма, происходит перераспределение памяти. Как правило,
  это приводит к тому, что вектор выделяет новую область хранения,
  перемещая элементы и свободные старые области в новый участок памяти.


Wiki

Можно ли это назвать хеш-таблицей. Если нет то почему ?

Почитал кормена и написал хеш-таблицу на основе сцепления элементов. Можно ли это назвать хеш-таблицей и если нет то почему, какие ошибки есть логические ? node.hpp #ifndef NODE_HPP #define NODE_HPP
template class list;
template class node { private: friend class list;
private: node* m_next; node* m_prev; T m_data;
public: node() : m_next(0) , m_prev(0) , m_data(0) {}
explicit node(T d) : m_next(0) , m_prev(0) , m_data(d) {} T get_data() { return m_data; } };
#endif // NODE_HPP list.hpp #ifndef LIST_HPP #define LIST_HPP
#include #include
#include "node.hpp"
template class list { private: node* m_head; node* m_tail; unsigned m_size;
public: list() : m_size(0) , m_head(0) , m_tail(0){}
node* get_new_node(T d) const; node* find(T data) const; void insert_at_front(T data); void insert_at_back(T data); void delete_at_front(); void delete_at_back(); bool is_empty() const; void print() const; node* get_begin() const { return m_head; } node* get_end() const { return m_tail; } unsigned get_size() const { return m_size; } };
template node* list::get_new_node(T data) const { node* n = new node(data); assert(n != 0); return n; }
template bool list::is_empty() const { if(m_head == 0) { return true; } return false; }
template void list::print() const { if(is_empty()) { return; } node* t = m_head; while(t != 0) { std::cout << t->m_data << " "; t = t->m_next; } }
template node* list::find(T data) const { if(is_empty()) { return 0; } node* t = m_head; while(t != 0 && t->m_data != data) { t = t->m_next; } return t; }
template void list::insert_at_front(T data) { node* n = get_new_node(data); if(m_head == 0) { m_head = m_tail = n; n->m_next = n->m_prev = 0; ++m_size; } else { n->m_next = m_head; if(m_head != 0) { m_head->m_prev = n; } m_head = n; n->m_prev = 0; ++m_size; } }
template void list::insert_at_back(T data) { node* n = get_new_node(data); if(m_tail == 0) { m_head = m_tail = n; n->m_next = n->m_prev = 0; ++m_size; } else { m_tail->m_next = n; n->m_prev = m_tail; m_tail = n; ++m_size; }
}
template void list::delete_at_front() { if(is_empty()) { return; } else { node* t = m_head->m_next; t->m_prev = 0; delete m_head; m_head = t; --m_size; } }
template void list::delete_at_back() { if(is_empty()) { return; } else { node* t = m_tail->m_prev; t->m_next = 0; delete m_tail; m_tail = t; --m_size; } }
#endif // LIST_HPP hash_table.hpp #ifndef HASH_TABLE_HPP #define HASH_TABLE_HPP
#include "list.hpp"
template class hash_table { private: list** m_table; unsigned m_size;
private: int get_hash(int key);
public: explicit hash_table(unsigned); T find(const T&, const T&); void insert(const T&, unsigned); void remove(const T&); };
template hash_table::hash_table(unsigned size) { m_size = size; m_table = new list*[m_size]; for(int i = 0; i < m_size; ++i) { m_table[i] = new list(); } }
template int hash_table::get_hash(int key) { return (key % m_size); }
template T hash_table::find(const T& d, const T& i) { int h = get_hash(i); node* n = m_table[h]->find(d); assert(n != 0); return n->get_data(); }
template void hash_table::insert(const T& d, unsigned key) { unsigned h = get_hash(key); m_table[h]->insert_at_front(d); }
#endif // HASH_TABLE_HPP Поправил код find(...) template T hash_table::find(const T& i) { int h = get_hash(i); if(m_table[h]->get_begin() != 0) { return m_table[h]->get_begin()->get_data(); } return 0; } но так получается что функция всегда возвращает только голову списка а если есть коллизия то этот случай не учитывается ... ?

Ответ

Есть несколько замечаний по реализации: Непонятна сигнатура find(T, T). Почему не find(Key)? Непонятно ваше разделение для элементов хэш-таблицы. То есть, сигнатуры методов должны выглядеть как insert(Key, Value) / find(Key) / remove(Key), либо как insert(Value) / find(Value) / remove(Value) для случая, когда в хэш-таблице хранятся не пары ключ-значение, а сами значения. Других вариантов нет. Не предложена имплементация remove(T). Вместо траты времени на реализацию своего std::list, лучше бы уж написали метод удаления элементов из хэш-таблицы. Крайне странное решение, в котором вызов функции find() coredump'ится в случае отсутствующего в хэш-таблице значения. Вообще, предложенный код, за исключением последних пятнадцати строчек, не имеет к хэш-таблицам никакого отношения, а просто предлагает какой-то неочевидный способ реализации аналога std::list. Решение с наследованием node ← list, кстати, кажется очень странным. А так, ну да, обычная хэш-таблица с chaining'ом для резолвинга коллизий.

Как создать гибкую схему таблиц для хранения сообщений из разных чатов?

Помогите пожалуйста разобраться в следующей ситуации:
Есть два вида API где хранятся истории сообщений, это Zopim и Chat2Desc(импортировать в Postman) . Пока эти два но могут потом и другие появится.
И моя ДБ с таблицей users
Table users id , email, phone, ...
В Zopim пользователи идентифицируются через email, a в Chat2Desc через телефон. Для меня эти два поля важны, какой бы чат не был и сколько бы их не было.
То есть если я получаю емайл либо телефон пользователя в сообщениях, то делаю запрос в свою базу (table users) для идентифицирования своего пользователя.
Да и в принципе даже структура чатов не важна, я данные как нибудь да выберу.А вот как их правильно сохранить , да так чтоб у меня была одна структура для всех .
И вот что я придумал:
Разъяснение:
Таблица chats (Данные для чата) :
client_id - указывает на id таблицы chat_clients duration - длительность чата system_type - хранит имя чата (Zopim, Chat2Desc, ... ) created_at - дата создания
Таблица chat_clients (сведений об пользователей которые были в чате):
assigned_data - те инициалы под которыми пользователи были в чате is_agent - (0 | 1): 1 => мой пользователь, 0 => не мой users_id - id пользователя. Содержит либо id из таблицы users либо пустой. bean_module - неважно (сведение о моём пользователе) unique_col - Тут будет либо email (из Zopim) либо телефон (из Chat2Desc, Либо думаю хранить id таблицы users).Будет гарантировать уникальность значений.
Связка users_id + unique_col уникальна (UNIQUE KEY user_id_unique_col_UQ (user_id,unique_col))
Таблица chat_messages
text - текст сообщения. client_id - указывает на id таблицы chat_clients chat_id - указывает на id таблицы chats file_id - указывает на id таблицы chat_files transport - значение будет для Chat2Desc (Viber, WhatsApp ,...), для Zopim ,чтоб не пустовал , Zopim
Таблица chat_files Сведения о переданных файлах в чате.Aналогичных таблиц может быть может нет для хранения дополнительной инфы.
Доп инфо: В дальнейшем собираюсь для каждого пользователя выводит историю сообщений.
Вопрос: Как создать гибкую схему таблиц для хранения сообщений из разных чатов ?
Заранее благодарю.

Ответ

Любые проблемы по созданию БД нужно разбивать на две части:
Нужно выделить то, что уже есть. Выделить данность, реальность. То, что вы не можете изменить. То есть, выделить структуру внешних данных. Нужно выделить то, что вы хотите получить. Желаемый вид и форма.
У вас в структуре всё в одной куче. И материальное представление, и логический вид. Вам нужно выделить отдельные структуры под хранения данных из каждой отдельной системы чатов, которые вы поддерживаете. Так как структуры от­личаются ключами привязки к пользователям, это должны быть разные структуры. Нет, ко­не­чно, можно всё сделать в одной таблице, но тут вы ничего не приобретёте, но очень про­иг­ра­ете в сложности структуры. Если вам нужно делать уникальный ключ по двум ко­лонкам, то вы что-то делаете не так.
Затем нужно выделить то, что вы хотите получить. Значить вам нужна какая-то таблица свя­зки чатов и пользователей, и таблицы связки чатов в основной таблице и чатов в мате­риаль­ных таблицах. Если нужно хранить сообщения в каждом чате для быстрого доступа, то лучше будет это сделать явно, в отдельной таблице, не связанной с материальным пред­став­лением. Так сообщения будут храниться два раза, но вы не будете связаны материальным пред­став­лением после импорта сообщений, и ваш код получения данных из БД будет много проще и надёжней.
В современном мире нет смысла пытаться оптимизировать число таблиц в БД: если у вас их будет десять или сотня, само по себе это нисколько не повлияет на скорость работы с БД. Другое дело что сложная для понимания структура БД будет отнимать ваше время и на первоначальную разработку, и на дальнейшую поддержку. Если траты вашего времени можно избежать, то это следует сделать.
Сама сложная структура БД может представлять и сложность при масштабировании. Например, шардинг и уникальные индексы идут по разные стороны улицы: вы не можете использовать шардинг одновременно с уникальными индексами. То же можно сказать про скорость вставки записей: уникальные индексы ей не помогают.

разница list и array

Можно ли говорить об общих различиях между типами данных list и array независимо от языка программирования? В частности, по способу доступа к элементам? В Python что является "истинным" списком -- list или tuple? Какая из этих структур требует больше памяти и при каких условиях?

Ответ

Строго говоря, связный список и массив - это различные структуры данных, которые не привязаны к конкретному языку программирования.
Массив
Массив - это совокупность однотипных данных, расположенных непрерывно в памяти. Доступ к элементу осуществляется по индексу за O(1) - мы обращаемся непосредственно к нужному участку памяти.
Связанный список
Доступ к элементу в связном списке в среднем занимает O(N) путем перебора элементов в поисках нужного. Способы доступа к элементам отличаются по реализации и от языка программирования. Например, на Java в стандартном классе LinkedList в зависимости от ситуации проход элементов может начинаться как с начала, так и с конца списка. И поиск элемента может осуществляться как по индексу, так и по сравнению элементов.
Связный список требует больших расходов памяти при прочих равных условиях за счет хранения указателей на следующий/предыдущий элементы и особенностей внутренней реализации.
Что касается Python: согласно документации
Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move).
Как видим, внутренне list представляет собой массив, для tuple - аналогично.