질문 : 파이썬 리스트 처리 속도를 향상시키는 방법?

처음 쓰는 글이네요. 약간 질문이 횡설수설해도 양해해 주시면 감사하겠습니다.
먼저 제 질문을 요약하자면 [a, b, c, d]와 같은 일정한 길이의 리스트 수십만 개를 요소로 가지는 리스트 A가 있다면 이 리스트 A 안의 리스트들을 골라내되, 골라낸 리스트들 중 리스트들의 앞 2개의 요소가 중복되는 경우가 없도록(리스트 A에 중복되는 리스트들이 있는 경우 랜덤으로 하나만 선택) 골라내는 빠른 방법이 무엇인지에 대한 것입니다.

사실 이미 일정 부분에 대해 중복없이 골라내는것을 구현은 했는데 이게 리스트 A의 길이가 짧을 때는 잘 작동하다가 길이가 수십만이 되니까 너무 오래 걸려서 어떻게 할지 잘 모르겠네요…

제가 지금 neat알고리즘(https://towardsdatascience.com/neat-an-awesome-approach-to-neuroevolution-3eca5cc7930f)을 가지고 육목(https://en.wikipedia.org/wiki/Connect6)을 플레이하는 AI를 진화시키는 프로그램을 만들고 있는데요, 부모 신경망을 교차시켜 자식 신경망을 만들도록 했는데 바둑판 크기에 맞게 신경망이 입력받는 크기와 출력받는 크기를 362(흑돌을 잡았는지 백돌을 잡았는지 입력하기 위해 길이 361의 보드 상태에 추가로 1개의 요소가 더 들어감), 361로 설정하니까 입력층 노드 2개, 출력층 노드 3개 정도에서는 아주 잘 작동하던게 속도가 너무 느려집니다.

crossover를 수행하는 함수는

def crossover(parent1, parent2):
    child_connection = []
    all_connection = copy.deepcopy(parent1.connection) + copy.deepcopy(parent2.connection)
    #같은 노드들에 대한 연결이 존재하는지 확인하기 위한 리스트
    overlap_connection = []
    #자식 신경망의 은닉층 노드들의 갯수를 세기 위한 리스트
    overlap_hidden_node = []
    child_hidden_size = 0
    #한 신경망의 연결만 자식 신경망에게로 전달되는것을 막기 위해 연결을 섞는다.
    random.shuffle(all_connection)
    for i in all_connection:
        if i[ : 2] not in overlap_connection:
            overlap_connection.append(i[ : 2])
            child_connection.append(i)
            #자식 신경망의 은닉 노드 갯수 조사
            for node in i[ : 2]:
                if parent1.input_size <= node < (parent1.input_size + parent1.hidden_size):
                    if node not in overlap_hidden_node:
                        child_hidden_size += 1
                        overlap_hidden_node.append(node)
    #자식 신경망 객체 생성
    child = ann(parent1.input_size, parent1.output_size)
    child.connection = copy.deepcopy(child_connection)
    child.hidden_size = child_hidden_size
    child.apply_change()
    return child

이렇게 생겼습니다.
신경망에서 연결은 [node1, node2, weight, True]처럼 저장되는데 이렇게 되면 node1에서 node2로 weight를 가중치로 가지는 연결이 활성화되었다는 것입니다.
이 함수에서는 두 부모 신경망의 연결을 불러와 합쳐 all_connection으로 저장한 뒤, 랜덤으로 섞고(이렇게 해야 한 부모로부터만 모든 연결이 전달되는 것을 막을 수 있기 때문에) all_connection을 순회하면서 child_connection에 이전에 추가된 연결들 중에서 현재 검사중인 연결과 node1과 node2가 같은 연결이 없다면 그대로 child_connection에 추가하고, 밑 부분에서 자식 신경망의 은닉 노드 갯수를 검사하는 부분은 아마 속도에 별 영향을 주지 않는 듯 합니다.
부모 신경망의 연결들 중에서 같은 노드끼리의 연결은 둘 중 하나만 선택하도록 하고 싶습니다.

+혹시 몰라서 전체 코드도 추가합니다

import math, random, copy
def crossover(parent1, parent2):
    child_connection = []
    all_connection = copy.deepcopy(parent1.connection) + copy.deepcopy(parent2.connection)
    #같은 노드들에 대한 연결이 존재하는지 확인하기 위한 리스트
    overlap_connection = []
    #자식 신경망의 은닉층 노드들의 갯수를 세기 위한 리스트
    overlap_hidden_node = []
    child_hidden_size = 0
    #한 신경망의 연결만 자식 신경망에게로 전달되는것을 막기 위해 연결을 섞는다.
    random.shuffle(all_connection)
    for i in all_connection:
        if i[ : 2] not in overlap_connection:
            overlap_connection.append(i[ : 2])
            #child_connection.append(i)
            #자식 신경망의 은닉 노드 갯수 조사
            for node in i[ : 2]:
                if parent1.input_size <= node < (parent1.input_size + parent1.hidden_size):
                    if node not in overlap_hidden_node:
                        child_hidden_size += 1
                        overlap_hidden_node.append(node)
    #자식 신경망 객체 생성
    child = ann(parent1.input_size, parent1.output_size)
    child.connection = copy.deepcopy(child_connection)
    child.hidden_size = child_hidden_size
    child.apply_change()
    return child

def get_random_weight():
    return random.random() * 10 - 5

def sigmoid(x):
    return 1 / (1 + math.exp(-x))

class ann:
    def __init__(self, input_size, output_size, p = 0.6):
        self.input_size = input_size
        self.hidden_size = 0
        self.output_size = output_size
        self.node_size = self.input_size + self.hidden_size + self.output_size
        self.connection = []
        #연결을 랜덤으로 설정한다.
        for i in range(0, input_size):
            for j in range(input_size, input_size + output_size):
                if random.random() <= p:
                    self.connection.append([i, j, get_random_weight(), True])
        self.connection_structure = self.get_connection_structure()
        #self.connection_structure은 self.process_order이 설정되기 전에 설정되어야 한다.
        self.process_order = self.get_process_order()
        #올바른 연결 추가를 위해 노드를 층별로 분리한다.
        #self.connection_structure은 self.layer이 설정되기 전에 설정되어야 한다.
        self.layer = self.get_layer()
        #각 노드 번호의 인덱스에 그 노드가 속한 레이어 층 번호가 저장됨.
        self.node_layer = [0 for i in range(0, self.node_size)]
        for index, i in enumerate(self.layer):
            if i != []:
                for j in i:
                    self.node_layer[j] = index

    def get_connection_structure(self):
        connection_structure = [[] for i in range(0, self.node_size)]
        for i in self.connection:
            if i[3]:
                connection_structure[i[0]].append([i[1], i[2]])
        return connection_structure

    def get_process_order(self):
        process_order = []
        node = [i for i in range(0, self.node_size)]
        node_next = [i for i in range(0, self.node_size)]
        node_connection = [0 for i in range(0, self.node_size)]
        node_connection_check = [0 for i in range(0, self.node_size)]
        for i in self.connection:
            if i[3]:
                node_connection[i[1]] += 1
        while node_connection != node_connection_check or node != []: #출력층의 경우를 빠뜨리지 않도록 조건 or로 추가.
            for i in node:
                if node_connection[i] == node_connection_check[i]:
                    node_next.remove(i)
                    process_order.append(i)
                    
                    for j in self.connection_structure[i]:
                        node_connection_check[j[0]] += 1
            node = node_next
        return process_order

    def get_layer(self):
        #레이어별로 분류
        layer = []
        #계산과정을 위한 리스트(레이어 값 기록)
        layer_split = [1 for i in range(0, self.node_size)]
        layer_split_final = []
        #각 노드에 대해 그 노드에 입력을 주는 노드들의 목록
        input_node_list = [[] for i in range(0, self.node_size)]
        for i in self.connection:
            if i[3]:
                input_node_list[i[1]].append(i[0])
        #각 노드에 대해 (그 노드에 입력을 주는 노드의 레이어 값의 최댓값 + 1)을 기록
        #이런 방식으로 레이어 별 분류가 가능함
        for i in self.process_order:
            if input_node_list[i] != []: #만약 입력을 주는 노드가 없을 경우에 대비한 예외처리 추가
                layer_split[i] = max([layer_split[k] for k in input_node_list[i]]) + 1
        #출력층에 대해 마지막 층으로 분류되도록 조정
        max_layer_value = max(layer_split)
        for i in range(self.input_size, self.input_size + self.output_size): 
            layer_split[i] = max_layer_value
        #레이어 값을 기반으로 레이어 분류
        for i in range(max(layer_split)):
            layer.append([])
        for node, i in enumerate(layer_split):
            layer[i - 1].append(node)
        return layer

    def propagate(self, input_data):
        node = [0 for i in range(0, self.node_size)]
        node[ : self.input_size] = input_data
        for i in self.process_order:
            if i >= self.input_size:
                node[i] = sigmoid(node[i])
                if self.connection_structure[i] != []:
                    for j in self.connection_structure[i]:
                        node[j[0]] += node[i] * j[1]
            else:
                for j in self.connection_structure[i]:
                    node[j[0]] += node[i] * j[1]
        return node[self.input_size + self.hidden_size : self.node_size]

    def mutate(self, p = 0.1):
        if random.random() <= p:
            self.mutate_add_node()
        if random.random() <= p:
            self.mutate_add_connection()
        if random.random() <= p:
            self.mutate_remove_connection()
        if random.random() <= p:
            self.mutate_change_weight()
        if random.random() <= p:
            self.mutate_slight_change_weight()

    def mutate_add_node(self):
        if self.connection != []:
            is_mutatable = False
            for i in self.connection:
                if i[3]:
                    is_mutatable = True
                    break
            #활성화된 노드가 존재한다면
            if is_mutatable:
                #먼저 연결을 하나 고르고
                #연결이 활성화된 연결로 선택될때까지 계속 고르기를 반복한다.
                con = random.choice(self.connection)
                while not con[3]:
                    con = random.choice(self.connection)
                con_index = self.connection.index(con)
                self.connection[con_index][3] = False
                self.hidden_size += 1
                self.connection.append([con[0], self.node_size, 1, True])
                self.connection.append([self.node_size, con[1], con[2], True])
                self.apply_change()

    def mutate_add_connection(self): #연결 추가
        only_connection = []
        for i in self.connection:
            if i[3]:
                only_connection.append(i[ : 2])
        input_node = random.randint(0, self.input_size + self.hidden_size - 1)
        output_node = random.randint(0, self.node_size - 1)
        trail = 0
        succeed = True
        while self.node_layer[input_node] >= self.node_layer[output_node] or [input_node, output_node] in only_connection:
            trail += 1
            output_node = random.randint(0, self.node_size - 1)
            if trail >= 1000:
                succeed = False
                break
        if succeed:
            self.connection.append([input_node, output_node, get_random_weight(), True])
            self.apply_change()

    def mutate_remove_connection(self): #연결 제거
        if self.connection != []:
            remove_con = random.choice(self.connection)
            self.connection.remove(remove_con)
            self.apply_change()

    def mutate_change_weight(self): #가중치 변경
        if self.connection != []:
            change_con = random.choice(self.connection)
            con_index = self.connection.index(change_con)
            self.connection[con_index][2] = get_random_weight()
            self.apply_change()

    def mutate_slight_change_weight(self): #가중치 변경
        if self.connection != []:
            change_con = random.choice(self.connection)
            con_index = self.connection.index(change_con)
            self.connection[con_index][2] += (random.random() * 2 - 1)
            self.apply_change()

    def apply_change(self):
        self.node_size = self.input_size + self.hidden_size + self.output_size
        self.connection_structure = self.get_connection_structure()
        #self.connection_structure은 self.process_order이 설정되기 전에 설정되어야 한다.
        self.process_order = self.get_process_order()
        #올바른 연결 추가를 위해 노드를 층별로 분리한다.
        #self.connection_structure은 self.layer이 설정되기 전에 설정되어야 한다.
        self.layer = self.get_layer()
        #각 노드 번호의 인덱스에 그 노드가 속한 레이어 층 번호가 저장됨.
        self.node_layer = [0 for i in range(0, self.node_size)]
        for index, i in enumerate(self.layer):
            if i != []:
                for j in i:
                    self.node_layer[j] = index

a = ann(362, 361)
b = ann(362, 361)
c = crossover(a, b)

요약 질문 부분만 답변드리면, [a, b, c, d]를 삽입할 때 dictionary에 (key: [a, b], value: [a, b, c, d])와 같이 삽입하시면 됩니다.
랜덤으로 하나 고르는건 랜덤한 값을 하나 뽑아서 특정 값보다 작으면 삽입하는 방식으로 진행하시면 됩니다.

추가로 말씀드리면, NEAT에서는 노드와 간선을 새로 추가하면서 점점 크기가 커집니다. 이 크기의 제한을 걸지 않으면 정말 무한정으로 커질 수 있으니, 제약 조건을 적절하게 설정해야 합니다.

답변 감사합니다. 그런데 리스트는 딕셔너리에서 키로 사용될 수 없는 것 같은데 어떻게 하면 될까요? 일단 str(리스트) 형식으로 바꿔서 딕셔너리에서 키로 쓰도록 다시 수정해 봤는데 여전히 속도는 별로 개선이 안됩니다ㅠㅠ 뭔가 방법이 있을까요?

사실 아까 전까지는 그냥 HyperNEAT로 바꿀까 생각중이었는데 어쩌면 정말 그래야 될지도 모르겠네요. 그건 가중치 생성하는 신경망은 크기가 작아서 지금 방식으로도 문제가 없을 거니까요.

리스트는 안되지만, 튜플은 될겁니다.
키 타입의 기준이 값이 변할 수 있는지를 따지는거라서요

고맙습니다, 근데 다시 시도해봐도 속도는 여전히 느리네요 ㅠㅠ 어쩌면 애초에 이렇게 큰 규모의 네트워크에 대해서 NEAT를 쓰겠다는 거 자체가 별로 맞는 게 아닐수도 있는 것 같아요. 사실 아까 답변 확인하기 전에 잠깐 HyperNEAT를 구현해봤는데 이건 넘파이를 쓰다 보니까 속도도 규모에 비해서 빠르고 가중치를 생성하는 신경망은 규모가 작다 보니까 문제없이 교차도 작동하더라고요. 일단은 HyperNEAT를 쓰는 쪽으로 방향을 바꿔야겠네요.
아무튼 답변 달아주셔서 정말 감사합니다.