Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 23 24 25 26 27 28 [29] 30 31 32   вперед  Ctrl
 Re: Для чего нужен питон?  [new]
Холивар масдай!
Guest
Ура, пасаны! Юбилейная мессага! ЖЖоте!
28 апр 08, 15:05    [5604430]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
просабмитил перл:
@array = <>;

1450760 2008-04-28 13:13:59 Sorting Bank Accounts wrong answer  2.77  74M  PERL

time = 2.77s (> 1.31s > 0.60s)

Осталось только понять почему у питона потребленная память помечена как всего лишь 3.8М
28 апр 08, 15:25    [5604549]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
В голову полез бред и я решил вот так проверить питон (а вдруг он внаглую не весь инпут читает?):

import sys
z=sys.stdin.readlines()

from random import randint
print z[randint(0,len(z)-1)]

--result:

1450795 2008-04-28 13:31:00 Sorting Bank Accounts wrong answer  0.86  4.6M  PYTH

большой разницы не видно; непонятки с памятью
28 апр 08, 15:34    [5604628]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
Гость_0
Guest
ретти

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
using namespace std;
vector<string> vs;

int main() {
    while (true) {
        char line[50];
        if (!fgets(line,50,stdin)) break;
        vs.push_back(line);
    }
return 0;
}
а вот такое принципиально не хотите сравнивать ?
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<string*> vs;

int cmp(const string *const a, const string *const b)
{
    return strcmp(a->c_str(), b->c_str());
}

int main() {
    while (true) {
        char line[50];
        if (!fgets(line,50,stdin)) break;
        vs.push_back(new string(line));
    }

stable_sort(vs.begin(), vs.end(), cmp);

return 0;
}
:)
28 апр 08, 16:36    [5605129]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
щас сравню и доложу через 7 минут
28 апр 08, 16:56    [5605249]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
Время сортировки такое же как и у питона 2.75-2.85с
Только почему в *vs[0] НЕ наименьшая строка из файла?
Гляньте что не так:
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <ctime>
using namespace std;
vector<string*> vs;

int cmp(const string *const a, const string *const b)
{
    return strcmp(a->c_str(), b->c_str());
}

FILE *fp=fopen("D:\\v.txt","r");

int main() {
    while (true) {
        char line[50];
        if (!fgets(line,50,fp)) break;
        vs.push_back(new string(line));
    }
    fclose(fp);

    double t;
    t=clock()/CLOCKS_PER_SEC;
     stable_sort(vs.begin(), vs.end(), cmp);
    cout << clock()/CLOCKS_PER_SEC-t << endl;

    int m;
    cin >> m;               ---- ввожу 0
    cout << *vs[m];       -------- получаю не ту строку
    getchar();
return 0;
}
28 апр 08, 17:16    [5605326]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
Гость_0
Guest
сорри, я накосячил :)
пусть будет так:
bool cmp(const string *const a, const string *const b)
{
    int r = strcmp(a->c_str(), b->c_str());
    return r <= 0;
}
28 апр 08, 18:26    [5605612]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
щас наверное будет Ок
Я кстати свои 3.03с (очень неплохо) получил сортируя именно указатели,
правда юзал я qsort из stdlib.h + массив (никаких векторов). У кого время меньше,
те явно сортировали не квиксортом, а чем-то самопальным или разбивали bank account на части и т.д.
Кстати, мое решение потянуло всего 6 мегов памяти; так что, 3.8М у питона вполне реально.
28 апр 08, 18:34    [5605638]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
Японский бох. Я скоро ёпнусь.
Теперь сортирует правильно, НО резко увеличилось время сортировки: чуть-чуть меньше 8с.
Т.е., всё вернулось взад.
28 апр 08, 18:40    [5605651]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
А вот так кстати лучше

bool cmp(const string *a, const string *b)
{
    return *a < *b;
    --//int r = strcmp(a->c_str(), b->c_str());
    --//return r <= 0;
}

И 8с заменяются на ~6.15с
Т.е., выигрыш от сортировки указателей равен 8.5с - 6.2с = 2.3с
Солидно,.. но до сцуки-питона все-таки далековато.
28 апр 08, 19:44    [5605768]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
А если вернуть назад sort() вместо stable_sort(), то уже никакого выигрыша нет.
Те же 7.5с. Хотя на практике merge (stable) чаще медленнее qsort.
И в нашем случае применять stable вообще никакого смысла нет.
28 апр 08, 20:30    [5605829]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
Green2
Member

Откуда: skype: green2x2
Сообщений: 13749
2 ретти
В чём тайный смысл такой оптимизации?
Я например, знаю, что если создать алгоритм в ПЛИС (программируемые логические интегральные схемы) то он будет ещё быстрее, и к тому же работать параллельно. Но мало кто так делает.
--
Картинка с другого сайта.

Posted via ActualForum NNTP Server 1.4

29 апр 08, 11:26    [5607174]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
Ёш
Member

Откуда:
Сообщений: 2892
ретти
А вот так кстати лучше
это потому что время сортировки зависит от входных данных, а операторы < и <= дадут разные входные данные при одном и том же файле ;)

ps: попробуйте ещё "по приколу" посортировать функцией
bool cmp(const string *a, const string *b)
{
    return true;
}
29 апр 08, 11:57    [5607452]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
Ёш
ретти
А вот так кстати лучше
это потому что время сортировки зависит от входных данных, а операторы < и <= дадут разные входные данные при одном и том же файле ;)

ps: попробуйте ещё "по приколу" посортировать функцией
bool cmp(const string *a, const string *b)
{
    return true;
}

для моего файла это не важно (< или <=) -- в нем нет дубликатов

под "лучше" я имел в виду лучше без .c_str() и соответственно без strcmp()
29 апр 08, 13:08    [5608045]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
Green2
2 ретти
В чём тайный смысл такой оптимизации?
Я например, знаю, что если создать алгоритм в ПЛИС (программируемые логические интегральные схемы) то он будет ещё быстрее, и к тому же работать параллельно. Но мало кто так делает.
--
Картинка с другого сайта.
Posted via ActualForum NNTP Server 1.4

ничего не понял; ты про какую оптимизацию?
29 апр 08, 13:13    [5608100]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
Кажется, True надо возвращать только когда arg1 строго меньше arg2 (если хотим stable):
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

vector<string> vs;

bool cmp(const string &a, const string &b)
{
    return a.substr(1,1) <= b.substr(1,1); -- сортируем по второму символу
}

int main() {
    vs.push_back("05");
    vs.push_back("10");
    vs.push_back("20");
    vs.push_back("30");
    vs.push_back("40");
    vs.push_back("50");

    stable_sort(vs.begin(), vs.end(), cmp);

    for (int i=0; i<vs.size(); ++i)
        cout << vs[i] << endl;

    getchar();
    return 0;
}


50
40
30
20
10
05
(stable_)sort() подает на вход cmp() ПЕРВЫЙ аргумент ВСЕГДА с БОЛЬШИМ индексом?
29 апр 08, 18:50    [5610806]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
Green2
Member

Откуда: skype: green2x2
Сообщений: 13749
ретти> ничего не понял; ты про какую оптимизацию?
Я про оптимизацию времени выполнения программы.
По моему, важнее иметь понятную работающую программу,
а скорость работы - это улучшение железа.
--
Картинка с другого сайта.

Posted via ActualForum NNTP Server 1.4

30 апр 08, 10:17    [5612247]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
Ну что-же :) внесу и я скромную лепту в измерение Хвостов
(Поскольку просто так мерять хвосты было скууууушна, забацал
маааааленькую лямбду. Просто так, для удовольствия )

DEBUG

stable_sort (string): 2.0520445
sort (string): 2.2701138
stable_sort (string*): 0.2398043
sort (string*): 0.2728142


RELEASE

stable_sort (string): 0.1881270
sort (string): 0.2052382
stable_sort (string*): 0.0072493
sort (string*): 0.0084706


Думаю, теперь можно считать доказанным, чтио STL маструбирует с СОДЕРЖИМЫМ строк в памяти, а stable_sort совсем не обязательно медленнее sort.

Выводы делайте сами, успехов в Труде

К сообщению приложен файл (Sort.zip - 6Kb) cкачать
30 апр 08, 13:32    [5613750]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71782
Gluk (Kazan)
Ну что-же :) внесу и я скромную лепту в измерение Хвостов
(Поскольку просто так мерять хвосты было скууууушна, забацал
маааааленькую лямбду. Просто так, для удовольствия )

DEBUG

stable_sort (string): 2.0520445
sort (string): 2.2701138
stable_sort (string*): 0.2398043
sort (string*): 0.2728142


RELEASE

stable_sort (string): 0.1881270
sort (string): 0.2052382
stable_sort (string*): 0.0072493
sort (string*): 0.0084706


Думаю, теперь можно считать доказанным, чтио STL маструбирует с СОДЕРЖИМЫМ строк в памяти, а stable_sort совсем не обязательно медленнее sort.

Выводы делайте сами, успехов в Труде

А вот это вот

stable_sort (string*): 0.0072493
sort (string*): 0.0084706

точно сортирует по значению строк, а не указателей??
30 апр 08, 14:11    [5614052]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
XDiaBLo
точно сортирует по значению строк, а не указателей??


Проверь код лямбды
Я проверял выплевыванием на экран небольшой выборки
нормально сортирует

P.S. Кстати указания на ошибки, недочеты и пр. преветствуются
30 апр 08, 14:31    [5614193]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71782
Gluk (Kazan)
XDiaBLo
точно сортирует по значению строк, а не указателей??


Проверь код лямбды
Я проверял выплевыванием на экран небольшой выборки
нормально сортирует

P.S. Кстати указания на ошибки, недочеты и пр. преветствуются

Крайне любопытные результаты :)
30 апр 08, 14:33    [5614200]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
XDiaBLo
Крайне любопытные результаты :)


Да, меня тоже слегка удивило.
Но дальше копать сегодня не хочу
30 апр 08, 14:37    [5614228]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71782
Gluk (Kazan)
XDiaBLo
Крайне любопытные результаты :)


Да, меня тоже слегка удивило.
Но дальше копать сегодня не хочу

Компилятор то хоть какой был?
30 апр 08, 14:38    [5614234]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
XDiaBLo
Gluk (Kazan)
XDiaBLo
Крайне любопытные результаты :)


Да, меня тоже слегка удивило.
Но дальше копать сегодня не хочу

Компилятор то хоть какой был?


Ну Други Мои там же солюшн целиком лежит совсем совсем мааааленький
MSVC 2003
30 апр 08, 14:45    [5614291]     Ответить | Цитировать Сообщить модератору
 Re: Для чего нужен питон?  [new]
ретти
Guest
У меня не компилится поскольку не тот компилер.
Если прицепишь экзешник чтоб читал строки из D:\v.txt, то я сравню.

2.
А вот похоже петон-батон сортирует-то втихаря указатели, а не буквально перемещает
строки туда-сюда.
id(object)

Return the ``identity'' of an object. This is an integer (or long integer) which is guaranteed to be unique and constant for this object during its lifetime.
(Implementation note: this is the address of the object.)

>>> v = ['zzz', 'aaa']

>>> print id(v[0]), id(v[1])

12292800 12295392

>>> v.sort()

>>> print id(v[0]), id(v[1])

12295392 12292800
30 апр 08, 15:56    [5614858]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 23 24 25 26 27 28 [29] 30 31 32   вперед  Ctrl
Все форумы / Программирование Ответить