[C#] Problem z wydajnością (stara nazwa: [C++] Problem ze wskaźnikami)
Siema,
zapomniało mi się już trochę C++, a raczej operowanie wskaźnikami i mam lekkiego problema.
Zadanie ma taką treść:
Cytuj:
Przypuśćmy, że budujemy nowoczesną światłowodową sieć szkieletową. Jeśli przesył odbywa się tylko poprzez tą sieć, to opóźnienia komunikacyjne są pomijalne. Te zalety powodują, że sieć rozwija się bardzo dynamicznie. Twoje zadanie polega na napisaniu oprogramowania, które odpowie czy dane dwa adresy IP łączy sieć czysto światłowodowa.
Wejście
Wejście składa się z wierszy, z których każdy zawiera informację o budowie nowego połączenia lub zapytanie o istnienie połączenia.
Informacja o budowie nowego łącza ma postać
B IP1 IP2,
gdzie IP1 i IP2 to adresy IP (w formacie czterech liczb z zakresu 1..255 oddzielonych kropkami), pomiędzy którymi powstaje łącze. Na początku działania programu sieć nie zawiera żadnych łączy.
Zapytanie o istnienie połączenia światłowodowego ma natomiast postać
T IP1 IP2.
Wejście kończy się wraz z końcem pliku.
Wyjście
Na każde zapytanie należy wypisać w osobnym wierszu T lub N w zależności, czy dane dwa adresy IP łączy sieć światłowodowa, czy też nie.
Jest też przykład wejścia i wyjścia:
Cytuj:
Wejście:
B 100.100.100.1 100.100.100.2
B 100.100.100.1 100.100.100.3
B 100.100.100.10 100.100.100.11
T 100.100.100.1 100.100.100.3
T 100.100.100.10 100.100.100.2
T 100.100.100.10 100.100.100.11
B 100.100.100.11 100.100.100.2
T 100.100.100.10 100.100.100.3
T 100.100.100.100 100.100.100.103
Wyjście:
T
N
T
T
N
I mój programik który dla tych danych testowych działa bez problemu:
Kod:
#include <vector>
#include <iostream>
#include "string.h"
using namespace std;
class Node
{
public:
char* Value;
bool WasVisited;
vector<Node*> Neighbors;
Node(char* value)
{
Value = new char[strlen(value) + 1];
strcpy(Value, value);
WasVisited = false;
}
};
static bool FindWithinNighbours(vector<Node*> queue, char* ip);
static bool Connected(char* ip1, char* ip2);
static Node *FindByValue(char* value);
static Node *AddNode(char* value);
static void AddUndirectedEdge(char* from, char* to);
static void CheckConnection(char* line);
static void ProcessLine(char* line);
static void AddConnection(char* line);
static vector<Node*> graph;
static char** split(char *text)
{
char **tab = new char*[2];
int ip1len = 0, ip2len = 0;
strtok(strdup(text), " ");
for(int i = 2; i < strlen(text); i++)
{
if(text[i] != ' ')
{
ip1len++;
}
else
{
ip2len = strlen(text) - i - 1;
break;
}
}
tab[0] = new char[ip1len];
tab[1] = new char[ip2len];
strcpy(tab[0], strtok(strdup(NULL), " "));
strcpy(tab[1], strtok(strdup(NULL), " "));
return tab;
}
static Node *FindByValue(char* value)
{
int size = graph.size();
bool isAny = false;
for(int i = 0; i < size; i++)
{
if(strlen(graph[i]->Value) != strlen(value))
continue;
for(int j = 0; j < strlen(graph[i]->Value); j++)
{
if (graph[i]->Value[j] != value[j])
{
isAny = false;
break;
}
isAny = true;
}
if(isAny)
return graph[i];
}
return NULL;
}
static Node *AddNode(char* value)
{
Node *node = new Node(value);
graph.push_back(node);
return node;
}
static void AddUndirectedEdge(char* from, char* to)
{
Node *fromNode = FindByValue(from);
if (fromNode == NULL)
fromNode = AddNode(from);
Node *toNode = FindByValue(to);
if (toNode == NULL)
toNode = AddNode(to);
fromNode->Neighbors.push_back(toNode);
toNode->Neighbors.push_back(fromNode);
}
static void CheckConnection(char* line)
{
char** parts = split(line);
if (Connected(parts[0], parts[1]))
printf("T");
else
printf("N");
for(int i = 0; i < sizeof(parts); i++)
delete parts[i];
delete parts;
}
static void ProcessLine(char* line)
{
if (line[0] == 'T')
CheckConnection(line);
else
AddConnection(line);
}
static void AddConnection(char* line)
{
char** parts = split(line);
AddUndirectedEdge(parts[0], parts[1]);
for(int i = 0; i < sizeof(parts); i++)
delete parts[i];
delete parts;
}
static bool Connected(char* ip1, char* ip2)
{
Node *node = FindByValue(ip1);
if (node == NULL)
return false;
for(int i = 0; i < graph.size(); i++)
graph[i]->WasVisited = false;
vector<Node*> temp;
temp.push_back(node);
return FindWithinNighbours(temp, ip2);
}
static bool FindWithinNighbours(vector<Node*> queue, char* ip)
{
bool isAny = false;
while (queue.size() != 0)
{
Node node = *queue[0];
if(strlen(node.Value) == strlen(ip))
{
for(int j = 0; j < strlen(node.Value); j++)
{
if (node.Value[j] != ip[j])
{
isAny = false;
break;
}
isAny = true;
}
if(isAny)
return true;
}
queue.front() = queue.back();
queue.pop_back();
for(int i = 0; i < node.Neighbors.size(); i++)
{
if(!node.Neighbors[i]->WasVisited)
{
queue.push_back(node.Neighbors[i]);
node.Neighbors[i]->WasVisited = true;
}
}
}
return false;
}
int main()
{
while (true)
{
char line[256];
cin.getline(line, 128);
char* input = new char[strlen(line) + 1];
strcpy(input, line);
if (input == "e")
break;
ProcessLine(input);
delete input;
}
return 0;
}
Problem występuje w momencie gdy do programu ładujemy za dużo danych. Ciężko mi to przetestować bo nie mam tego zestawu, ale może ktoś bardziej ogarnięty znajdzie tu gdzieś memory leaki czy coś w tym stylu?
Treść mojego błędu:
"segmentation fault", najczęstszy błąd (przekroczenie dozwolonego obszaru pamięci, etc...);
lub dokładniej:
a) użycie niezainicjowanego wskazania
int * pInt;
*pInt = 5; // dup !
b) użycie przedawnionego wskazania
int * pInt = new int;
...
delete pInt;
...
cout << *pInt; // dup !
c) wyjście poza tablicę (najczęściej w pętli)
int array[4] = {0,1,2,3};
array[4] = 4; // dup !
d) użycie znullowanego wskazania
int * pInt = 0;
*pInt = 3; // dup !
