логи профайлера в студию;-)

на первый взгляд в main прячется N^2 операций, так что ничего удивительного тут нет.

А просто взять список, вставить в него элементы, отсортировать и убрать дубликаты - не катит? Обязательно нужно сделать из Питона Си?

Тогда уже взять set, вставить все что нужно и бахнуть по нему sorted;-)

> Тогда уже взять set

А какая разница?

Ну в set дубликаты убираются автоматом сразу по мере добавления. Для больших N это может давать выигрышь, правда элементы наск я помню должны быть хэшируемые.

профайлер вот чего пишкт:

LinkedList = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 
	4.5
         6010 function calls in 4.196 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     2000    0.012    0.000    0.012    0.000 2.py:12(__init__)
        1    0.000    0.000    0.000    0.000 2.py:17(__init__)
        1    0.016    0.016    0.016    0.016 2.py:25(RemoveDuplicates)
        1    0.000    0.000    0.000    0.000 2.py:40(__str__)
        1    4.128    4.128    4.196    4.196 2.py:50(main)
     2000    0.004    0.000    0.004    0.000 :0(random)
        1    0.000    0.000    0.000    0.000 :0(range)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        2    0.000    0.000    0.000    0.000 :0(time)
        1    0.000    0.000    4.196    4.196 <string>:1(<module>)
        1    0.000    0.000    4.196    4.196 profile:0(main())
        0    0.000             0.000          profile:0(profiler)
     2000    0.036    0.000    0.040    0.000 random.py:351(uniform)

И чего Вам не нравится? У Вас в main сортировка стоит. Добавьте добавление с сортировкой отдельным методом в свой список, увидите что все там и высадится.

ну да, похоже, так оно и есть :-) я сделал простое выделение памяти для нод без сортировки, так память оказывается выделяется без проблем

def main():
  t1 = time.time()
  L  = LinkedList()

  for i in range ( 0, 10000 ): 
    if L.first == None:
        L.last  = Node(i,None)
        L.first = Node(i,L.last)
    else:
        new = Node(i,None)
        L.last.next = new
        L.last = new
  
  print L

  t2 = time.time()
  print "\t%.1f" % ((t2 - t1))

я почему написал этот пост: у меня есть эквивалент этого алгоритма, написанный на си
так вот там та же сортировка практически НЕ тормозит

казалось бы: в питоне все переменные одновременно являются ссылками
бери и пользуйся
но вот ран-тайм в питоне оказывается желает быть ...

> так вот там та же сортировка практически НЕ тормозит

Сортировка или проход по списку?

>> Сортировка или проход по списку?

добавление случайной ноды в отсортированном порядке
т.е. во время итерации по списку происходит вставка новой ноды в нужную позицию

> т.е. во время итерации по списку происходит вставка новой ноды в нужную позицию

Ну а чего ты ждал? В Си проход по списку - это несколько инструкций в цикле, а в Питоне - куча тяжелых обращений к атрибутам.

Втупую переписывать код с Си на Питон - как минимум глупо.

Гхм... а чем Вам родной питоновский список не угодил?

>> Гхм... а чем Вам родной питоновский список не угодил?

родной питоновский список и связный список - это как бы несколько разные весовые категории

> родной питоновский список и связный список - это как бы несколько разные весовые категории

Связный список - супертяж? %)

С алгоритмической ТЗ Вы конечно правы. Но де-факто, накладные расходы на поддержку Вашей конструкции в питоне на порядки превышают весь выигрыш (как по памяти, так и по быстродействию). Хотите чего то более быстрого чем встроенный питоновский список - пишите свой на С/С++ и импортируйте в питон.

>> Связный список - супертяж? %)

это две разных сущности
например, в стандартном питоновском списке доступ к произвольному элементу есть величина постоянная и не зависящая от величины массива

> например, в стандартном питоновском списке доступ к произвольному элементу есть величина постоянная и не зависящая от величины массива

И чем это мешает в твоей задаче?

>> И чем это мешает в твоей задаче?

оно не мешает
задача - создать СВЯЗНЫЙ отсортированный список, а не стандартный отсортированный питоновский список

А чем по функциональности питоновский список отличается от связного?

Скоростью операций вставки/удаления отличается. Не зря же вот такое реализуют: http://pypi.python.org/pypi/blist/

>> А чем по функциональности питоновский список отличается от связного?

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

> задача - создать СВЯЗНЫЙ отсортированный список, а не стандартный отсортированный питоновский список

Скорее задача заключается в том, чтобы СОЗДАТЬ связный список и сказать «Питон тормоз, чтд».

Это я не тестил. Ну тогда делайте свой на С++ и включайте в питон при помощига SWIG-а например. http://a-iv.ru/pyart/cpp2py.pdf

>> Скорее задача заключается в том, чтобы СОЗДАТЬ связный список и сказать «Питон тормоз, чтд».

ну в общем да
как оказалось, перенос алгоритмов из низкоуровневого языка в высокоуровневый похоже не всегда себя оправдывает

> как оказалось, перенос алгоритмов из низкоуровневого языка в высокоуровневый похоже не всегда себя оправдывает

Особенно, если их переносить буквально.

>> Особенно, если их переносить буквально.

ну как буквально ?
связный список - он и в африке связный список

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

>> Особенно, если их переносить буквально.

ну как буквально ?

Так, как сделал ты. Ты вообще понимаешь, что в Python запись obj.attr - это поиск в словаре? И еще раз - зачем ты используешь самодельный список? Ты думаешь, что он будет быстрее, или даст гарантии, или что? Только не надо мне читать лекций о том, что такое связный список, если перед этим хотя бы не посмотрел на релизацию списка в Python.

>ну как буквально ?

связный список - он и в африке связный список

Ага. Буквально это так как Вы сделали. Напр если нода будет парой [value,next] уже будет быстрее. Если прикрутите функц прогр для сортировки и вставки - будет еще быстрее.

[..] от величины массива

какого, простите, массива?

Что-то я сделал

class Node(object):
   __slots__ = ('value', 'next')
   # далее по тексту

class LinkedList(object):
   __slots__ = ('first', 'last', 'length', 'ins', 'old', 'curr')
   # далее по тексту

ну и еще по мелочи (== None поменял на is None, например, True и False, там где булевские проверки).

Моментальное ускорение раза эдак в 4.

Короче, затык у тебя где-то в мозгу

Питон — это не Перл.
Питон — это не Си.
Питон — это не Ява.

Питон — это Питон.

Пруф:

import profile
import random 
import time


class Node(object):
    __slots__ = ('value', 'next')
    def __init__(self, value = None, next = None):
        self.value = value
        self.next = next

class LinkedList(object):
    __slots__ = ('first', 'last', 'length', 'ins', 'old', 'curr')
    def __init__(self):
        self.first = None
        self.last  = None
        self.length = 0
        self.ins = 0
        self.old  = None
        self.curr = None

    def __str__(self):
        if self.first is not None:
            current = self.first
            out = 'LinkedList = ' + str(current.value)
            while current.next is not None:
                current = current.next
                out = out + ' ' + (str(current.value))
            return out
        return ''

    def insert(self, somevalue):
        if self.first is None:
            self.first = Node(somevalue, None)
        elif self.first.value > somevalue:
            self.first = Node(somevalue, self.first)
        else:
            old = curr = self.first
            ins=False
            while curr is not None:
                if curr.value == somevalue:
                    return
                elif curr.value > somevalue:
                    curr = Node(somevalue, curr)
                    old.next = curr
                    ins = True
                    break
                old = curr
                curr = curr.next
            if not ins:
                curr = Node(somevalue, None)
                old.next = curr

def main():
  t1 = time.time()
  L  = LinkedList()
  for i in range ( 0, 2000 ) : 
    _r = int ( random.uniform ( 0, 100 ) )
    L.insert(_r)
  print L
  t2 = time.time()
  print "\t%.1f" % ((t2 - t1))


profile.run('main()')

Почему-то стабильно дает результаты в 0.13 сек., тогда как твоя версия 4.7 сек. ЧЯДНТ?