Функция C++ возвращает результат очень медленно, намного медленнее, чем функционально эквивалентный код Python. ⇐ Python

[Anonymous]

У меня есть функция, которая используется в скрипте, который я пишу, для удаления избыточных блокирующих ключевых слов из списка. По сути, с вводом (в любом порядке):

Код: Выделить всё

{"apple", "bapple", "banana", "cherry", "bananaman", "sweetherrypie", "sweet", "b"}

Он должен вывести сжатый массив строк (в любом порядке):

Код: Выделить всё

{"apple", "cherry", "sweet", "b"}

Это сделано для того, чтобы уменьшить количество ключевых слов, которые алгоритм сопоставления должен пройти в рамках личного учебного проекта (если строка содержала слово «банан», она также будет содержать « b", поэтому банан не нужен и его можно выбросить.
Он должен был быть чрезвычайно производительным, поскольку ему приходилось работать со списками, содержащими более 10 000 000 строк.
Изначально я написал для этого код на Python:

Код: Выделить всё

def deduplicate_keywords(keywords):
# Remove duplicates and sort the keywords by length in ascending order
keywords = sorted(set(keywords), key=len)
unique_keywords = []

for keyword in keywords:
not_redundant = True

for unique_keyword in unique_keywords:
# Check if the current keyword includes any of the unique keywords
if unique_keyword in keyword:
not_redundant = False
break
# If the keyword does not include any of the shorter keywords, add it to unique_keywords
if not_redundant:
unique_keywords.append(keyword)

return unique_keywords

И тест производительности для измерения производительности:

Код: Выделить всё

class TestDeduplicateKeywords(unittest.TestCase):
def test_performance_intensive_case(self):
keywords = [
"abcdef",
"def",
"ghidef",
"jkl",
"mnop",
"qrst",
"uvwxyz",
"ghijkl",
"abcdefgh",
"ijklmnop",
"mnopqrstuv",
"rstuvwx",
"mnopqrstuvwx",
"uvwx",
]

# Extending the list to make it very long and complex
base_keywords = keywords[:]
for i in range(200000):
base_keywords.extend([f"{k}{i}" for k in keywords])
base_keywords.extend([f"{i}{k}" for k in keywords])
base_keywords.extend([f"{i}{k}{i}" for k in keywords])

keywords = base_keywords

old_function_time = 0
new_function_time = 0

for repeat in range(1):
# This loop (not present in the cpp code) is used to loop it multiple times to find an average
start_time = time.time()
result = deduplicate_keywords(keywords)
end_time = time.time()
old_function_time = (
repeat * old_function_time + (end_time - start_time)
) / (repeat + 1)
start_time = time.time()
result = deduplicate_keywords_new(keywords)
# Above is a function that can be edited to check whether changes speed up the code
end_time = time.time()
new_function_time = (
repeat * new_function_time + (end_time - start_time)
) / (repeat + 1)

# As the list is extended with numbers, the result will be unique non-redundant keywords
expected_result = ["def", "jkl", "mnop", "qrst", "uvwx"]

self.assertEqual(set(result), set(expected_result))
print(
f"Test performance_intensive_case for old function took {old_function_time} seconds\n"
f"Test performance_intensive_case for new function took {new_function_time} seconds\n"
)

if old_function_time < new_function_time:
print(f"Old is faster than new")
else:
print(f"New is faster than old")

if __name__ == "__main__":
unittest.main()

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

Код: Выделить всё

#include 
#include 
#include 
#include 
#include 
#include 
#include 

std::vector deduplicate_keywords(const std::vector& keywords) {
auto t_start = std::chrono::high_resolution_clock::now();

// Remove duplicates using a set
auto t1 = std::chrono::high_resolution_clock::now();
std::cout 

Подробнее здесь: [url]https://stackoverflow.com/questions/78812814/c-function-returns-extremely-slowly-far-slower-than-functionally-equivalent-p[/url]