2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Блокировки
Сообщение16.06.2017, 12:07 


04/05/13
125
rockclimber
Если опустить скучные детали считывания данных, то:
У меня есть структура для блокировок, которая хранит диапазон заблокированных ресурсов и время, когда они освободятся.
Я создаю вектор из таких структур и каждую новую блокировку, если она принята, добавляю в вектор.
Процесс принятия/отклонения блокировки такой: я прохожусь по вектору блокировок и рассматриваю каждый элемент. Если блокировка уже неактивна, то удаляю ее, и перехожу к следующей. Если она активна, то смотрю, не пересекается ли она с новой блокировкой. Если пересекается, то вывожу No и выхожу из цикла, если не пересекается, то перехожу к следующей блокировке из вектора.
Если я так и не нашел активную блокировку, которая пересекается с новой блокировкой, то добавляю новую блокировку в вектор и печатаю Yes.

Появилась другая идея: попробую отсортировать массив по уменьшению времени и дойдя до неактивной блокировки буду отсекать хвост. Но уже вечером. Если сработает, напишу сюда. Спасибо за помощь Geen, rockclimber :-)

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 12:10 
Заслуженный участник
Аватара пользователя


01/09/13
4318
inky в сообщении #1226067 писал(а):
Если блокировка уже неактивна, то удаляю ее, и перехожу к следующей.

Не совсем так - удаляю и начинаю поиск заново.... ;-)

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 12:13 


04/05/13
125
Geen
Ааа, точно... :facepalm: спасибо, что заметили это.
Жаль, я уже выехал из дома. Чуть позже попробую это исправить.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 12:16 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
А, еще хотел спросить. Не лучше ли этот код
Код:
int intersects(vector<block>::const_iterator it, int start, int end) {
    if ((start <= it->start && it->start <= end) ||
        (start <= it->end   && it->end   <= end)) {
        return 1;
    }
    return 0;
}
Записать как
Используется синтаксис C++
bool intersects(vector<block>::const_iterator it, int start, int end) {
    return (start <= it->start && it->start <= end) ||
           (start <= it->end   && it->end   <= end);
}
?
То есть оптимизатор может и сам оптимизирует, но лучше на всякий случай писать сразу нормально.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 12:21 


04/05/13
125
rockclimber
Да, вы правы. Мой косяк :oops:

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 12:24 
Заслуженный участник
Аватара пользователя


01/09/13
4318
А ещё лучше инлайном и с правильным условием из двух сравнений :-)

-- 16.06.2017, 12:26 --

inky в сообщении #1226067 писал(а):
попробую отсортировать массив по уменьшению времени

А по номерам ресурсов отсортировать тоже неплохо :-)

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 12:27 
Заслуженный участник


04/03/09
906
Проблема в неправильном выборе структуры данных. У вас с массивом блокировок производятся следующие операции: итерирование, вставка в конец, удаление из середины. А доступ к произвольному элементу не используется. Значит, вам нужен не массив, а список.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 13:20 
Заслуженный участник
Аватара пользователя


01/09/13
4318
12d3 в сообщении #1226076 писал(а):
Проблема в неправильном выборе структуры данных.

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

12d3 в сообщении #1226076 писал(а):
Значит, вам нужен не массив, а список.

Я бы, всё же, что-нибудь отсортированное сделал для более быстрого поиска занятых блоков...

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 13:28 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Geen в сообщении #1226091 писал(а):
Я бы, всё же, что-нибудь отсортированное сделал для более быстрого поиска занятых блоков...
Во время поиска пересечений новой блокировки с уже существующими запоминать в отдельную переменную место, куда вставить, если блокировка подойдет. Если блокировка подходит, вставлять в запомненное место. Тогда список будет сохраняться отсортированным.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 13:38 


04/05/13
125
Geen в сообщении #1226075 писал(а):
А ещё лучше инлайном и с правильным условием из двух сравнений :-)

Исправил :-) Переписал таким образом:
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
int block_me(vector<block> *blocked, int time, int start, int end, int duration, int istart) {
    for (int i = istart; i < blocked->size(); ++i) {
        if (blocked->at(i).time <= time) {
            blocked->erase(blocked->begin() + i);
            return block_me(blocked, time, start, end, duration, i);
        }
        if (!(blocked->at(i).start < start && blocked->at(i).end < start) &&
            !(blocked->at(i).start > end && blocked->at(i).end > end)) {
            cout << "No";
            return 1;
        }
    }
    block t = {
        .start = start,
        .end = end,
        .time = time + duration
    };
    blocked->push_back(t);
    cout << "Yes";
    return 0;
}
 


Правда, это не помогло. Все так же падает по времени на 17 тесте.

rockclimber, 12d3 Сейчас попробую переписать с отсортированным списком.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 13:46 
Заслуженный участник


04/03/09
906
Хм. Попробую прикинуть, что выгоднее.
Итак, на каждой итерации у нас происходит следующее:
a) Удаление старых блокировок.
b) Проверка новой блокировки на пересечение с имеющимися.
c) Добавление новой.
И разные варианты:
1. Несортированный массив.
2. Сортированный массив.
3. Несортированный список.
4. Сортированное дерево, сиречь set.
$\begin{array}{|c|c|c|c|}\hline  & a & b  & c \\ \hline  1 & O(N) & O(N) & O(1) \\ \hline  2 & O(N) & O(log(N)) & O(N) \\ \hline 3  & O(N) & O(N) & O(1) \\ \hline 4 & O(log(N)) & O(log(N) & O(log(N)) \\ \hline \end{array}$
Так что я был неправ, нужен set. Список лучше несортированного массива, но совсем чуть-чуть.
P.S. Считаем что за одну итерацию в среднем удаляется одна блокировка.
UPD. Ошибся в временем удаления в списке. Все равно нам надо просматривать все элементы в списке, чтоб найти, кого удалить.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 13:51 


04/05/13
125
rockclimber, 12d3, Geen
Использовал список, отсортировал его по убыванию времени -- если нахожу устаревшую блокировку, значит все последующие тоже неактивны, значит можно отрезать хвост. Но все равно падает по времени на 17-ом тесте..
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <iostream>
#include <list>

using namespace std;

struct block {
    int start, end, time;
};

bool compare_blocks (const block& first, const block& second) {
    return first.time >= second.time;
}

int block_me(list<block> *blocked, int time, int start, int end, int duration) {
    blocked->sort(compare_blocks);
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (it->time <= time) {
            blocked->erase(it, blocked->cend());
            break;
        }
        if (!(it->start < start && it->end < start) &&
            !(it->start > end && it->end > end)) {
            cout << "No";
            return 1;
        }
    }
    block t = {
        .start = start,
        .end = end,
        .time = time + duration
    };
    blocked->push_back(t);
    cout << "Yes";
    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    list<block> blocked;
    for (int i = 0; i < m; ++i) {
        int s, l, r, d;
        cin >> s >> l >> r >> d;
        block_me(&blocked, s, l, r, d);
        cout << endl;
    }
   
    return 0;
}
 

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 13:55 
Заслуженный участник
Аватара пользователя


01/09/13
4318
12d3 в сообщении #1226106 писал(а):
Удаление старых блокировок.

Необязательно. Нужно только если возникает пересечение с добавляемой.

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 13:56 


04/05/13
125
Geen в сообщении #1226112 писал(а):
Нужно только если возникает пересечение с добавляемой.

Я удаляю их, если пересечений не возникает :-)

 Профиль  
                  
 
 Re: Блокировки
Сообщение16.06.2017, 13:57 
Заслуженный участник
Аватара пользователя


01/09/13
4318
12d3 в сообщении #1226106 писал(а):
Сортированное дерево, сиречь set.

У нас два конца - можно попытаться использовать...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 53 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group