Trädstruktur av inlägg

23 oktober, 2005

Hur gör man bäst en trädstruktur av inlägg i ett diskussionsforum? Trädstrukturen skall vara av samma typ som på Eforum.

Jag har idag tabellen:

f_messages:

msgid #

threadid (exempeltrådid: 1)

parentid

datum (åååå-mm-dd hh:ii:ss)

..fler fält..

Inlägg A (msgid: 1) är första inlägget i tråden och har parentid 0.

Inlägg B (msgid: 2) som är ett svar på inlägg A (msgid: 1) får parentid: 1. Inlägg C (msgid: 3) som är ett svar på inlägg B (msgid: 2) får parentid: 2.

Inlägg D (msgid: 4) som är ett svar på inlägg A (msgid: 1) får parentid: 1.

Inläggen skall sedan sorteras enligt följande struktur:

Inlägg A

- Inlägg B

-- Inlägg C

- Inlägg D

Hoppas att ni förstår hur jag menar. Idag gör jag trådningen/trädstrukturen i PHP, men det håller inte i längden. Antalet loopar den får göra är X^2 (där X är antal inlägg i tråden). Om en megastor tråd innehåller 350 inlägg så behöver jag hela 122500 loop med dagens sätt i PHP. Det håller inte.

Hur gör jag det på ett bättre sätt? Kan jag göra sorteringen direkt i SQL-frågan? Har ni något exempel på bättre tabellstruktur (som går enklare att sortera)? Hur görs det på Eforum?

Jag har verkligen fastnat på det här och verkar inte kunna komma på en vettig lösning.

_________

TicoRoman - Anfall är bästa försvar

[inlägget ändrat 2005-10-23 08:09:20 av TicoRoman]

[inlägget ändrat 2005-10-23 08:59:29 av TicoRoman]

23 oktober, 2005

Antalet loopar den får göra är X^2

Jo, det är förstås ingen bra variant. Nu använder jag inte just PHP så jag vet inte vilket stöd den har för klasser och olika typer av listor/vektorer, men följande är den variant jag använder i oo-språk

1. Skapa en klass Message där du lagrar den data som hör till ett inlägg, ex. Id, ParentId,Message, InDate, Author osv.

2. Skapa en associativ vektor (Messages) där nyckeln är MessageId och datat är ex. en enkel array eller queue av de Message-instanser som har nyckeln som ParentId

3. Läs in alla inlägg i tråden. För varje inlägg skapar du en instans newMessage av Message och lagrar den sist i den array/queue som ligger i Messages(newMessage.ParentId)

4. Skriv ut inläggen genom att anropa nedanstående rekursiva funktion för varje post i Messages som har ParentId=0

(Pseudo-kod)

FUNCTION WritePost (oMessage,nLevel)

------ BEGIN

-------------// Output message

-------------PrintMessage(oMessage,nLevel)

------------ // Output closest children if any

------------ IF Messages.ContainsKey(oMessage.Id)

-----------------BEGIN

--------------------- FOR EACH oMess IN Messages(oMessage.Id)

--------------------------BEGIN

------------------------------WritePost(oMess,nLevel+1)

--------------------------END

-----------------END

------ END

END FUNCTION

nLevel använder du i din Printfunktion för ex. indentering eller hur du nu väljer att representera varje subnivå.

[inlägget ändrat 2005-10-23 09:08:19 av Anjuna Moon]

23 oktober, 2005

Jo, det är förstås ingen bra variant.

Minst sagt. Det "fungerar" tillfredställande så länge det rör sig om några tusen loopar (upp till 100 inlägg), även om det förstås är en idiotisk metod ur prestandasynpunkt. Vilket jag insåg sent, men alla har väl rätt att klanta sig.

---

Tack för tipset Anjuna. Jag är ingen fena på klasser (vet i princip grunderna, mest teoretiskt, ganska snål praktisk erfarenhet), men visst borde det gå att göra i PHP, i alla fall PHP 5 som är "OO-vänlig". Jag ska läsa på och försöka förverkliga idén och testa.

Om inte annat, så har jag nu tack vare ditt inlägg fått en idé om hur jag kan lösa det på ett bättre sätt (tror jag) än nuvarande, ifall jag inte klarar av att förverkliga din idé med klasser.

_________

TicoRoman - Anfall är bästa försvar

23 oktober, 2005

Ok, jag sitter mest och slöar här, så jag ska browsa lite i PHP-manualen och se om jag kan få ihop några exempel, om det kan hjälpa på traven.

23 oktober, 2005

Det skulle vara jätteschyst, samtidigt känns det som att du får göra alldeles för mycket för att hjälpa mig. Men visst, har du tid, ork och vilja så, men känn dig inte "tvingad".

Tack igen.

_________

TicoRoman - Anfall är bästa försvar

23 oktober, 2005

I det här fallet är inte objekt nödvändiga, du kan lika hjärna använda en array (alla arrayer i PHP är associativa). Mao kan Anjunas Message-klass lika gärna vara en array med motsvarande fält. Sen skadar det förstås inte att lära sig OO, men det behövs inte just här.

23 oktober, 2005

I det här fallet är inte objekt nödvändiga, du kan lika hjärna använda en array

Jo, insåg just det när jag satt och bläddrade igenom manualsidorna för ex. Array.

EDIT: Kom dessutom på att jag blev sugen på att fortsätta spela Fahrenheit, söndagar är till för spel och inte tänkande, så exemplen får vänta

[inlägget ändrat 2005-10-23 09:53:02 av Anjuna Moon]

23 oktober, 2005

Nu har jag inte läst allt här så supernoggrannt så jag kanske missat nån detalj.

Om man tittar på hur ett forum används så borde "visning av en tråd" ske BETYDLIGT oftare än "skapa nytt inlägg"? Med tanke på det kanske man kan flytta en del av jobbet till den punkt i tiden då man skapar ett nytt inlägg?

Lägg till en tabell som som innehåller "trådar".

En post i den tabellen innehåller en lååååång (MLM ) lista av inläggsnummer.

Själva inläggen kan ju själva hålla reda på vilken "nivå" de skrivits in på, detta eftersom ett inlägg bara kan vara medlem i exakt en tråd.

Att rendera en tråd borde innebära en uppslagning av ett tråd-id för att få en lista av inläggsnummer och sedan en enkel loop för att hämta ut de enskilda inläggen.

Trådtabellen är ju i alla högsta grad redundant men för att skynda på saker tycker jag det borde vara helt ok att göra så. Plus det faktum att folk tittar på trådar betydligt oftare än de skapar inlägg.

23 oktober, 2005

Tack zerblat. Jag är i vanliga fall morgontrött, så jag har lite svårt att föreställa mig en sådan array nu. Kan du visa hur en sådan array skulle se ut för de fem (fyra var det visst) exempelinläggen i första inlägget i denna tråd?

__

Jag flyttar samtidigt denna tråd till forumet för PHP.

_________

TicoRoman - Anfall är bästa försvar

[inlägget ändrat 2005-10-23 09:54:13 av TicoRoman]

23 oktober, 2005

"OO" är ju inte mycket annat än "syntaktiskt socker" så det påverkar ju inte saken i sig, det går lika bra att lösa "OO" som "icke-OO".

Bortsett från det så har PHP4 hyffsat stöd för OO - arv och polymorfism stöds och det är väl det viktigaste tycker jag.

PHP5 har jag inte använt på med men det ska vara OO, rätt och slätt och utan mystiska undantag.

23 oktober, 2005

"OO" är ju inte mycket annat än "syntaktiskt socker"

Förvisso, fast per definition är väl alla högnivåspråk syntaktiskt sockrade varianter av språk på lägre nivåer. Dock får man ju med OO mycket bättre ordning och struktur så där man kan tycker jag man ska utnyttja möjligheten att använda det.

Däremot kanske det är så att de OO-möjligheter som finns i språk som PHP4 och ASP (inte så OO men jo det finns möjlighet att åtminstone skapa grundläggande klasser) inte är de effektivaste lösningarna. Det har jag faktiskt aldrig utvärderat (dumt nog, eftersom jag hade för vana att använda klasser extensivt på ASP-tiden)

23 oktober, 2005

Förvisso, fast per definition är väl alla högnivåspråk syntaktiskt sockrade varianter av språk på lägre nivåer. Dock får man ju med OO mycket bättre ordning och struktur så där man kan tycker jag man ska utnyttja möjligheten att använda det.

Absolut.

Vad jag menade var att det stöd som PHP4 har för OO inte påverkar om det går att göra i PHP4 eller inte. Jag kanske missuppfattade det du skrev tidigare "...vilket stöd PHP har för OO...".

23 oktober, 2005

Vad jag menade var att det stöd som PHP4 har för OO inte påverkar om det går att göra i PHP4 eller inte.

Ah, nu förstår jag vad du menade. Söndagsmorgonshjärnan efter en blöt lördag är lika effektiv som en tre månader gammal wettextrasa

23 oktober, 2005

Jag klurade lite på det här, och gjorde på följande sätt:

1. Läser in alla inlägg (i aktuell tråd) från databasen.

2. Loopar igenom resultatet och sparar det i arrayen $messages, enligt:

$messages[parentid] = msgid;

3. Sorterar (och skriver ut) inläggen enligt:

[color="#0000ff"]function[/color] write($oId, $level)
{
[color="#0000ff"]global[/color] $messages;

$level++;

[color="#0000ff"]foreach[/color]($messages[$oId] [color="#0000ff"]as[/color] $a => $
{
	[color="#006400"]# Skriver ut nivå och msgid (för att testa)[/color]
	[color="#0000ff"]echo[/color] "<br>".$level.": ".$b;

	[color="#006400"]# Kollar om det finns "barn" till [/color]
	[color="#006400"]# aktuell förälder, dvs om arrayen [/color]
	[color="#006400"]# är satt[/color]
	[color="#0000ff"]if[/color]([color="#0000ff"]isset[/color]($messages[$b]))
	{
		write($b, $level);
	}
}
}

[color="#006400"]# Börjar utskriften från början, dvs [/color]
[color="#006400"]# från det inlägget som har parentid 0[/color]
write(0, 0);

Jag vet inte om det var så ni menade, men antalet loopar är lika med antalet inlägg, vilket iaf gör mig ganska nöjd. Dessutom verkar sorteringen bli rätt.

Enda nackdelen är att jag måste läsa in data från databasen till en array ($messages), men det gjorde jag även tidigare.

_________

TicoRoman - Anfall är bästa försvar

[inlägget ändrat 2005-10-23 10:32:21 av TicoRoman]

23 oktober, 2005

Jag vet inte om det var så ni menade,

Jodå, principen ser ut precis som det jag föreslog.

EDIT: Sen är det ju bara att ex. skapa en array för varje data som hör till ett inlägg, som du använder för utskriften.

Typ

$Authors[msgid] = sAuthor;

$InDates[msgid] = dtInDate;

Enda nackdelen är att jag måste läsa in data från databasen till en array ($messages), men det gjorde jag även tidigare.

Jo, fast komplexitet av O(2n) är ju likställt med O(n) och är forfarande långt bättre än O(n^2).

Med mindre än att du, som lizardKng var inne på, omstrukturerar ordningen på posterna direkt i databasen vid nya inlägg så kommer du inte undan lindrigare.

[inlägget ändrat 2005-10-23 10:40:52 av Anjuna Moon]

23 oktober, 2005

Söndagsmorgonshjärnan efter en blöt lördag är lika effektiv som en tre månader gammal wettextrasa

Hehe, jag vet vad du menar :-)

23 oktober, 2005

EDIT: Sen är det ju bara att ex. skapa en array för varje data som hör till ett inlägg, som du använder för utskriften.

Typ

$Authors[msgid] = sAuthor;

$InDates[msgid] = dtInDate

Jag gjorde (eller kommer göra) faktiskt på följande sätt:

1. Jag skapar en array $messages som endast innehåller parentid som key och msgid som data. Enligt punkt 2 i föregående inlägg.

2. Inläggsdata sparade jag i $msgdata[msgid][fältnamn] = fältdata. För att inte behöva hårdkoda fältnamn så loopar jag igenom det med foreach:

[color="#0000ff"]while[/color]($datar = @[color="#ff0000"]mysql_fetch_assoc[/color]($data))
{
[color="#006400"]# Spara parentid och msgid[/color]
$messages[$datar['parentid']][] = $datar['msgid'];

[color="#006400"]# Spara inläggsdata[/color]
[color="#006400"]# Loopa genom existerande fält ($x)[/color]
[color="#006400"]# och spara data för dessa ($y).[/color]
[color="#0000ff"]foreach[/color]($datar [color="#0000ff"]as[/color] $x => $y)
{
	$msgdata[$datar['msgid']][$x] = $y;

}
}

Jag har inte upptäckt några svagheter än.

Jo, fast komplexitet av O(2n) är ju likställt med O(n) och är forfarande långt bättre än O(n^2).

Med mindre än att du, som lizardKng var inne på, omstrukturerar ordningen på posterna direkt i databasen vid nya inlägg så kommer du inte undan lindrigare.

lizardKngs förslag är ju förstås också en bra idé, men eftersom den nya lösningen känns blixtsnabb jämfört med det gamla (x^2) så nöjer jag mig för tillfället. Tack för alla tips! Det blev så mycket enklare.

_________

TicoRoman - Anfall är bästa försvar

[inlägget ändrat 2005-10-23 10:48:53 av TicoRoman]

23 oktober, 2005

Du verkar ha löst det, men här är ändå min snabbimplementation:

<?[color="#0000ff"]php[/color]
[color="#006400"]/* följande ska förstås läsas från db. Har bara med dem för att göra $messages-tilldelningen mindre rörig. */[/color]
$msg_a = [color="#0000ff"]array[/color]('id' => 1, 'parent_id' => -1, 'title' => 'Inlägg A'[color="#006400"]/*...*/[/color]);
$msg_b = [color="#0000ff"]array[/color]('id' => 2, 'parent_id' => 1, 'title' => 'Inlägg B'[color="#006400"]/* ...*/[/color]);
$msg_c = [color="#0000ff"]array[/color]('id' => 3, 'parent_id' => 2, 'title' => 'Inlägg C'[color="#006400"]/*...*/[/color]);
$msg_d = [color="#0000ff"]array[/color]('id' => 4, 'parent_id' => 1, 'title' => 'Inlägg D'[color="#006400"]/*...*/[/color]);

$messages = [color="#0000ff"]array[/color](1 => [color="#0000ff"]array[/color]($msg_b, $msg_d), 2 => [color="#0000ff"]array[/color]($msg_c));


[color="#0000ff"]echo[/color] "<ul>\n";
write_post($msg_a, 0);
[color="#0000ff"]echo[/color] "</ul>\n";

[color="#0000ff"]function[/color] write_post($message) {
    [color="#0000ff"]global[/color] $messages;

    [color="#0000ff"]echo[/color] "<li>{$message['title']}</li>\n";

    [color="#0000ff"]if[/color] ([color="#0000ff"]array[/color]_[color="#ff0000"]key[/color]_exists($message['id'], $messages)) {
      [color="#0000ff"]echo[/color] "<ul>\n";
      [color="#0000ff"]foreach[/color] ($messages[$message['id']] [color="#0000ff"]as[/color] $m) {
          write_post($m);
      }
      [color="#0000ff"]echo[/color] "</ul>\n";
    }
}

?>

[inlägget ändrat 2005-10-23 10:58:45 av zerblat]

23 oktober, 2005

...men i så fall är det bästa att använda nån form av sidcachning. Då slipper du i normalfallet göra nån rendering öht och visningen blir i princip O(1) (eller snarare O(antalet sammalagda tecken i tråden)). Trots rekursionen är ju Anjunas variant O(n), och det får du ju hur du än loopar igenom posterna.

23 oktober, 2005

Jo, visst är det så, när man tänker efter

23 oktober, 2005

Kanske ska tillägga att det visade sej (iaf hos mej) att array_key_exists() inte var nåt bra val. isset() är mycket snabbare. Här är ett litet test jag körde (10000 slumpade "inlägg", men utan databas):

[log]<?php

include 'bench.php';

list($time, $msg) = bench('gen_thread', 10000);

print $time;

list($time) = bench('print_thread', $msg);

print $time;

function gen_thread($num) {

$msg[] = array('id' => 0, 'parent_id' => -1, 'title' => 'Inlagg 0');

for ($i = 1; $i < $num; $i++) {

$parent_id = rand(0, $i-1);

$msg[] = array('id' => $i, 'parent_id' => $parent_id, 'title' => "Inlagg $i, svarar pa $parent_id");

}

return $msg;

}

function print_thread($msg) {

global $message_list;

foreach ($msg as $m) {

$message_list[$m['parent_id']][] = $m;

}

echo "<ul>\n";

write_post($msg[0]);

echo "</ul>\n";

}

function write_post($message) {

global $message_list;

echo "<li>{$message['title']}</li>\n";

if (isset($message_list[$message['id']])) {

echo "<ul>\n";

foreach ($message_list[$message['id']] as $m) {

write_post($m);

}

echo "</ul>\n";

}

?>[/log]...och bench.php (säkert inte optimal, men verkar funka):

[log]<?php

function microtime_float()

{

list($usec, $sec) = explode(' ', microtime());

return ((float)$usec + (float)$sec);

}

function bench($fun) {

$bench_args = func_get_args();

for ($i = 1; $i < count($bench_args); $i++) {

$args[] = $bench_args[$i];

}

$calibrate_begin = microtime_float();

$calibrate_end = microtime_float();

$overhead_time = $calibrate_end - $calibrate_begin;

$performance_begin = microtime_float();

$ret = call_user_func_array($fun, $args);

$performance_end = microtime_float();

$result_time = ($performance_end - $performance_begin) - $overhead_time;

return array(number_format($result_time, 4), $ret);

}

?>[/log]

Trädstruktur av inlägg

Rekommendera Poster

TicoRoman

Länk till kommentar

Dela på andra webbplatser

Anjuna Moon

Länk till kommentar

Dela på andra webbplatser

TicoRoman

Länk till kommentar

Dela på andra webbplatser

Anjuna Moon

Länk till kommentar

Dela på andra webbplatser

TicoRoman

Länk till kommentar

Dela på andra webbplatser

zerblat

Länk till kommentar

Dela på andra webbplatser

Anjuna Moon

Länk till kommentar

Dela på andra webbplatser

lizardKng

Länk till kommentar

Dela på andra webbplatser

TicoRoman

Länk till kommentar

Dela på andra webbplatser

lizardKng

Länk till kommentar

Dela på andra webbplatser

Anjuna Moon

Länk till kommentar

Dela på andra webbplatser

lizardKng

Länk till kommentar

Dela på andra webbplatser

Anjuna Moon

Länk till kommentar

Dela på andra webbplatser

TicoRoman

Länk till kommentar

Dela på andra webbplatser

Anjuna Moon

Länk till kommentar

Dela på andra webbplatser

lizardKng

Länk till kommentar

Dela på andra webbplatser

TicoRoman

Länk till kommentar

Dela på andra webbplatser

zerblat

Länk till kommentar

Dela på andra webbplatser

zerblat

Länk till kommentar

Dela på andra webbplatser

lizardKng

Länk till kommentar

Dela på andra webbplatser

zerblat

Länk till kommentar

Dela på andra webbplatser

Arkiverat

Vem är online 0 Medlemmar, 0 anonym, 30 gäster (Visa hela listan)

Populära medlemmar

Publika meddelanden

Senaste som Tittar

Senaste inlägg

Forum

Aktivitet

pcforalla.se