Once I kept repeatedly inputting a character in the search box, it is getting slower and slower until it hangs. I wanted to optimize it and make it smoother.
Can you guys help me or give me any advice for what I should do? I am getting the data correctly it just once I tried to search repeatedly without refreshing the page it is getting laggy.
This is my model:
public class TrieNode
{
public List<string> Titles { get; set; }
public Dictionary<char, TrieNode> Children { get; set; }
public bool IsEndOfWord { get; set; }
public int Popularity { get; set; }
public TrieNode()
{
Titles = new List<string>();
Children = new Dictionary<char, TrieNode>();
}
}
This is my service:
public void Insert(string title)
{
var node = _trie;
foreach (var ch in title)
{
if (!node.Children.ContainsKey(ch))
{
node.Children[ch] = new TrieNode();
}
node = node.Children[ch];
}
if (node.Titles != null)
{
node.Titles.Add(title);
}
else
{
node.IsEndOfWord = true;
}
if (node.Titles != null && node.Titles.Count >= Threshold)
{
ConvertListToTrie(node);
}
}
private void ConvertListToTrie(TrieNode node)
{
foreach (var title in node.Titles)
{
Insert(title);
}
node.Titles = null;
}
/* Search to get exact titles and with levenshtein then sort by latest visit first then popularity and titles asc then lastly with levenshtein*/
public List<(string title, int popularity)> Search(string prefix)
{
var node = _trie;
foreach (var ch in prefix)
{
if (!node.Children.ContainsKey(ch))
{
return new List<(string, int)>();
}
node = node.Children[ch];
}
return GettitlesFromNode(prefix, node);
}
private List<(string title, int popularity)> GettitlesFromNode(string prefix, TrieNode node)
{
var titles = new List<(string title, int popularity)>();
if (node.IsEndOfWord)
{
titles.Add((prefix, node.Popularity));
}
foreach (var child in node.Children.OrderByDescending(c => c.Value.Popularity))
{
titles.AddRange(GettitlesFromNode(prefix + child.Key, child.Value));
}
return titles;
}
public List<(string title, int popularity)> GetSuggestionsWithLevenshtein(string query)
{
var exactMatches = Search(query);
var additionalSuggestions = new List<(string title, int popularity)>();
if (exactMatches.Count < 10)
{
additionalSuggestions = FindSimilarTitles(query)
.Select(w => (title: w, popularity: GetPopularityFromTrie(w)))
.Where(w => !exactMatches.Any(s => s.title == w.title))
.Take(10 - exactMatches.Count)
.ToList();
}
return exactMatches.Select(s => (s.title, s.popularity))
.Concat(additionalSuggestions)
.OrderByDescending(s => s.popularity)
.ThenBy(s => s.title)
.ThenBy(s => Levenshtein(query, s.title))
.ToList();
}
/* Get Popularity and Last Visit of each title */
private int GetPopularityFromTrie(string title)
{
var node = _trie;
foreach (var ch in title)
{
if (!node.Children.ContainsKey(ch))
{
return 0;
}
node = node.Children[ch];
}
return node.IsEndOfWord ? node.Popularity : 0;
}
/* Find Titles with levenshtein distance */
private List<string> FindSimilarTitles(string input)
{
var results = new List<string>();
foreach (var title in GetAllTitles(_trie, ""))
{
if (Levenshtein(input, title) <= 2)
{
results.Add(title);
}
}
return results;
}
public List<string> GetAllTitles(TrieNode node, string prefix)
{
var titles = new List<string>();
if (node.IsEndOfWord)
{
titles.Add(prefix);
}
foreach (var child in node.Children)
{
titles.AddRange(GetAllTitles(child.Value, prefix + child.Key));
}
return titles;
}
private int Levenshtein(string input, string target)
{
if (input == target)
{
return 0;
}
if (input.Length == 0)
{
return target.Length;
}
if (target.Length == 0)
{
return input.Length;
}
int[,] distance = new int[input.Length + 1, target.Length + 1];
for (int i = 0; i <= input.Length; i++)
{
distance[i, 0] = i;
}
for (int j = 0; j <= target.Length; j++)
{
distance[0, j] = j;
}
for (int i = 1; i <= input.Length; i++)
{
for (int j = 1; j <= target.Length; j++)
{
int cost = input[i - 1] == target[j - 1] ? 0 : 1;
distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1, distance[i, j - 1] + 1), distance[i - 1, j - 1] + cost);
}
}
return distance[input.Length, target.Length];
}
This is my controller:
static TrieController()
{
var titles = System.IO.File.ReadAllLines("./assets/titles.txt");
foreach (var title in titles)
{
if (Regex.IsMatch(title, "^[a-z\s]+$", RegexOptions.IgnoreCase))
{
_trieService.Insert(title.ToLower());
}
}
}
[HttpGet]
public IActionResult GetSuggestions(string title)
{
var suggestions = _trieService.GetSuggestionsWithLevenshtein(title)
.Select(s => new { title = s.title, popularity = s.popularity });
return Ok(suggestions.Take(10));
}
This is the app.js:
let visitedTitles = JSON.parse(localStorage.getItem('visitedTitles')) || [];
/* Suggestions */
function getSuggestions()
{
const query = $('#search-box').val();
if (query.length === 0) {
$('#suggestions').empty();
return;
}
$.ajax({
//url: `http://ec2-3-25-135-98.ap-southeast-2.compute.amazonaws.com/trie/`,
url: `https://localhost:7223/trie/`,
data: { title: query },
success: function (data) {
displaySuggestions(data);
}
});
$('#clear-button').click(function()
{
$('#search-box').val('');
$('#suggestions').empty();
$(this).hide();
});
$('#search-box').on('input', function()
{
const query = $(this).val();
if (query.length > 0) {
$('#clear-button').show();
} else {
$('#clear-button').hide();
}
getSuggestions();
});
}
function displaySuggestions(suggestions)
{
const suggestionList = $('#suggestions');
suggestionList.empty();
const sortData = suggestions.map(title => {
const visitedItem = visitedTitles.find(item => item.title === title.title);
return {
...title,
visitDate: visitedItem ? visitedItem.date : null
};
});
sortData.sort((a, b) => {
const dateA = new Date(a.visitDate);
const dateB = new Date(b.visitDate);
if (isNaN(dateA.getTime()) && isNaN(dateB.getTime())) {
return 0;
} else if (isNaN(dateA.getTime())) {
return 1;
} else if (isNaN(dateB.getTime())) {
return -1;
} else {
return dateB.getTime() - dateA.getTime();
}
});
sortData.forEach(suggestion => {
const isVisited = visitedTitles.some(item => item.title === suggestion.title);
if (isVisited)
{
const visitedItem = visitedTitles.find(item => item.title === suggestion.title);
lastVisited = calculateTimeDifference(visitedItem.date);
}
const suggestionItems = $(
'<li class="list-group-item border-bottom d-flex btn btn-outline-success" width="200px;">' +
'<span class="suggestion-title "><i class="fa-solid fa-magnifying-glass fa-xs me-3" style="color: #c4c4c4;"></i>' + suggestion.title + '</span>' +
'<span class="text-body-tertiary ms-2" style="scale: 0.7;"><i class="fa-duotone fa-solid fa-eye fa-sm me-1"></i>' + suggestion.popularity + '</span>' +
'</li>'
);
if(isVisited) {
suggestionItems.addClass('visited');
}
suggestionList.append(suggestionItems);
});
$('#suggestions').on('click', 'li', function ()
{
const title = $(this).find('.suggestion-title').text();
const currentDate = new Date();
const gmtPlus8Date = new Date(currentDate.getTime() + 8 * 60 * 60 * 1000);
const formattedDate = gmtPlus8Date.toISOString().slice(0, 19);
const visitedItem = {
title: title,
date: formattedDate
};
visitedTitles.push(visitedItem);
getByName(title);
visitedTitles.push(title);
localStorage.setItem('visitedTitles', JSON.stringify(visitedTitles));
$('#search-box').val('');
$('#suggestions').empty();
});
}
$(document).ready(function()
{
const debouncedGetSuggestions = debounce(getSuggestions, 300);
$('#search-box').on('input', debouncedGetSuggestions, function() {
currentSearchPage = 1;
getSuggestions();
});
})